不是妹子 可以女装qwq

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
const int INF=0x7f7f7f7f;
struct Edge{
	int head[MAXN],to[MAXN*2],nxt[MAXN*2],vale[MAXN*2],tot;
	void add(int x,int y,int v){
		to[++tot]=y;
		vale[tot]=v;
		nxt[tot]=head[x];
		head[x]=tot;
	}
}G,T;
vector<pair<pair<int, int>, int> > Ne;
int dis[MAXN],n,m;
void build_tree(){	
	cin>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		G.add(x,y,z);
		G.add(y,x,z);
	}
	priority_queue<pair<int, int> > q;
	for(int i=1;i<=n;++i)
		dis[i]=INF;
	dis[1]=0;
	for(int i=1;i<=n;++i)
		q.push(make_pair(-dis[i],i));
	while(!q.empty()){
		int v=-q.top().first,p=q.top().second;
		q.pop();
		if(dis[p]<v)continue;
		for(int i=G.head[p];i;i=G.nxt[i])
			if(dis[G.to[i]]>dis[p]+G.vale[i]){
				dis[G.to[i]]=dis[p]+G.vale[i];
				q.push(make_pair(-dis[G.to[i]],G.to[i]));
			}
	}
	for(int p=1;p<=n;++p)
		for(int i=G.head[p];i;i=G.nxt[i]){
			if(dis[p]+G.vale[i]==dis[G.to[i]])
				T.add(p,G.to[i],G.vale[i]);
			else if(dis[p]==dis[G.to[i]]+G.vale[i])
				T.add(p,G.to[i],G.vale[i]);
			else Ne.push_back(make_pair(make_pair(p,G.to[i]),G.vale[i]));
		}
}
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN];
int top[MAXN],mp[MAXN],tot;
void dfs_build(int p){
	dep[p]=dep[fa[p]]+1;
	siz[p]=1;
	for(int i=T.head[p];i;i=T.nxt[i]){
		if(T.to[i]==fa[p])continue;
		fa[T.to[i]]=p;
		dfs_build(T.to[i]);
		siz[p]+=siz[T.to[i]];
		if(siz[son[p]]<siz[T.to[i]])
			son[p]=T.to[i];
	}
}
void dfs_top(int p){
	top[p]=son[fa[p]]==p?top[fa[p]]:p;
	mp[p]=++tot;
	if(son[p])dfs_top(son[p]);
	for(int i=T.head[p];i;i=T.nxt[i])
		if(T.to[i]!=son[p]&&T.to[i]!=fa[p])
			dfs_top(T.to[i]);
}
int a[MAXN*4],lazy[MAXN*4];
#define lson(p) ((p)<<1)
#define rson(p) ((p)<<1|1)
void pushdown(int p){
	if(!lazy[p])return;
	a[lson(p)]=min(a[lson(p)],lazy[p]);
	lazy[lson(p)]=min(lazy[lson(p)],lazy[p]);
	a[rson(p)]=min(a[rson(p)],lazy[p]);
	lazy[rson(p)]=min(lazy[rson(p)],lazy[p]);
	lazy[p]=0;
}
void modify(int x,int y,int l,int r,int v,int p){
	if(l<=x&&r>=y){
		lazy[p]=min(lazy[p],v);
		a[p]=min(a[p],v);
		return;
	}
	pushdown(p);
	int mid=(x+y)>>1;
	if(l<=mid)modify(x,mid,l,r,v,lson(p));
	if(r>mid)modify(mid+1,y,l,r,v,rson(p));
	a[p]=min(a[lson(p)],a[rson(p)]);
}
int query(int x,int y,int idx,int p){
	if(x==y)
		return a[p];
	pushdown(p);
	int mid=(x+y)>>1;
	if(idx<=mid)return query(x,mid,idx,lson(p));
	if(idx>mid)return query(mid+1,y,idx,rson(p));
}
void Modify(int x,int y,int v){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,n,mp[top[x]],mp[x],v,1);
		x=fa[top[x]];	
	}
	if(dep[x]<dep[y])swap(x,y);
	modify(1,n,mp[y]+1,mp[x],v,1);
}
int Find(int x){
	return query(1,n,mp[x],1);
}
int main(){
	build_tree();
	memset(a,INF,sizeof(a));
	dfs_build(1);
	dfs_top(1);
	for(int i=0;i<Ne.size();++i)
		Modify(Ne[i].first.first,Ne[i].first.second,dis[Ne[i].first.first]+dis[Ne[i].first.second]+Ne[i].second);
	int x;
	for(int i=2;i<=n;++i)
		printf("%d\n",(x=Find(i))==INF?-1:x-dis[i]);
}