B 最短路
先建出最短路 DAG，保证最短路径唯一，所以建出来的 DAG 是一棵树。考虑一个点的答案可以由谁来更新，假设当前点为点 \(u\)，它的 dfs 序控制范围是 \(l,r\)。首先，它可以由子树外除了父亲的节点来更新，形如 ans[u]=dis[v]+w，它也可以由子树内的节点更新，路径形如 1->zc->v->u，要求中转点 \(zc\) 必须在 \(u\) 的子树外，形式化的来说 \(ans_u=\min(dis_{zc}+w_{zc\to v})+w_{v\to u}[l\le dfn_{zc}\le r]\)，然后问题就成了一个单点修改，区间查询最小值的问题，从下往上线段树合并即可，时间复杂度 \(\mathcal{O}(n\log n)\)，常数比较小，比大部分正解要快。
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int RR(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353;
const int inf=1e18;
inline void Min(ll &x,ll y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,m,in[N],head[N],headg[N],tot,fa[N],L[N],R[N],dn,rub[N],num;
ll dis[N],ans[N];
struct EDGE{int v,next,w;}e[N<<2],g[N<<1];
inline void adde(int u,int v,int w){
e[++tot]={v,head[u],w};head[u]=tot;
}
inline void addg(int u,int v,int w){
g[++tot]={v,headg[u],w};headg[u]=tot;
}
bool vis[N],zhan[N<<2];
struct NODE{
int pos;
ll w;
inline bool operator<(const NODE &A)const{return w>A.w;}
};
std::priority_queue<NODE> q;
inline int fan(int x){if(x&1)return x+1;else return x-1;}
inline void dij(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;q.push({1,0});
while(!q.empty()){
int u=q.top().pos;q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
zhan[in[v]]=0;zhan[fan(in[v])]=0;
in[v]=i;zhan[in[v]]=zhan[fan(in[v])]=1;fa[v]=u;
if(!vis[v]){q.push({v,dis[v]});}
}
}
}
}
int root[N],cnt;
struct TREE{ll res;int ls,rs;}t[N*20];
inline int NEW(){int wk=num?rub[num--]:++cnt;t[wk]={inf,0,0};return wk;}
inline void Del(int &p){t[p]={inf,0,0};rub[++num]=p;}
inline void update(int p){
t[p].res=std::min(t[t[p].ls].res,t[t[p].rs].res);
}
inline void insert(int &p,int l,int r,int pos,ll x){
if(!p)p=NEW();
if(l==r){Min(t[p].res,x);return;}
int mid=l+r>>1;if(pos<=mid)insert(t[p].ls,l,mid,pos,x);
else insert(t[p].rs,mid+1,r,pos,x);update(p);
}
inline int merge(int a,int b,int l,int r){
if(!a||!b)return a|b;
if(l==r){Min(t[a].res,t[b].res);Del(b);return a;}
int mid=l+r>>1;
t[a].ls=merge(t[a].ls,t[b].ls,l,mid);
t[a].rs=merge(t[a].rs,t[b].rs,mid+1,r);
update(a);Del(b);return a;
}
inline ll query(int p,int l,int r,int L,int R){
if(t[p].res>=inf)return inf;
if(L>R)return inf;
if(l>=L&&r<=R)return t[p].res;
int mid=l+r>>1;ll res=inf;
if(L<=mid)Min(res,query(t[p].ls,l,mid,L,R));
if(R>mid)Min(res,query(t[p].rs,mid+1,r,L,R));
return res;
}
inline void init(int u){
L[u]=++dn;
for(int i=headg[u];i;i=g[i].next)init(g[i].v);
R[u]=dn;
}
inline void dfs(int u,ll dep){
for(int i=headg[u];i;i=g[i].next){
dfs(g[i].v,dep+g[i].w);
root[u]=merge(root[u],root[g[i].v],1,n);
}
if(u==1)return;
Min(ans[u],std::min(query(root[u],1,n,1,L[u]-1),query(root[u],1,n,R[u]+1,n))-dep);
int what=std::min(query(root[u],1,n,1,L[u]-1),query(root[u],1,n,R[u]+1,n));
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(zhan[i]||L[v]>=L[u]&&R[v]<=R[u])continue;
ll res=dis[v]+e[i].w;insert(root[u],1,n,L[v],res+dep);
Min(ans[u],res);
}
}
signed main(){
freopen("path.in","r",stdin);freopen("path.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),m=read();for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();adde(u,v,w);adde(v,u,w);}
dij();tot=0;for(int i=2;i<=n;++i)addg(fa[i],i,e[in[i]].w);
init(1);t[0].res=inf;for(int i=1;i<=n;++i)ans[i]=inf;
dfs(1,0);
for(int i=2;i<=n;++i)std::cout<<(ans[i]>=1e17?-1:ans[i])<<'\n';
}