Description：

给你一些点， 他们与节点 $1$ 的最短路的最后一条边不可走， 求每一个点到 $1$ 的最短距离。

保证最短路唯一。

$1\leqslant n\leqslant 10^5$

Solution：

题目里有一个奇怪的条件叫做最短路唯一，这说明把最短路图建出来是一棵以 $1$ 为根的有根树。

既然不能走从 $1$ 到某个点的最短路的最后一条边，那么一定经过了一条非树边，设它为 $(u,v,w)$ ，把他拆成两个有向边，设其中一个是 $(u\to v,w)$ ，考虑它会对哪些产生贡献， $1\sim u$ 肯定不行，因为经过了最短路最后一条边 $LCA$ 的子树之外的也不行，因为可以不走这一条边，肯定不优， $u$ 子树内和 $v$ 子树内就更不用说了，所以分析下来只有 $v$ 到 $LCA$ 的深一层的点是可能被更新的，如果用树链剖分 $+$ 线段树的话 $LCA$ 深一层的点不是很好处理，推一下式子会发现取 $\min$ 的是 $d[u]+w(u,v)+d[v]-d[t]$ ， $d[t]$ 无关可以不管，剩下的部分是一个只与这条边的情况有关的量，于是可以先把所有边排序，这样每个位置第一次被更新时就是答案，可以用并查集来跳过大段的已经处理好的部分。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

#define MAXM 200010

struct edges

{

	int u,v,w;

}es[MAXM];

struct edge

{

	int to,nxt,v;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int d[MAXN];

bool cmp_es(edges a,edges b){return d[a.u] + d[a.v] + a.w < d[b.u] + d[b.v] + b.w;}

bool v[MAXN];

int anc[MAXN];

#define INF 0x3f3f3f3f

int fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],dep[MAXN];

void dfs1(int k,int depth)

{

	siz[k] = 1;dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int ans[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		es[i].u = read();es[i].v = read();

		es[i].w = read();

		add(es[i].u,es[i].v,es[i].w);

	}

	priority_queue< pair<int,int> > q;

	memset(d,0x3f,sizeof(d));

	d[1] = 0;q.push(make_pair(0,1));

	int cnt = 0;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				anc[e[i].to] = k;

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	for(int i = 2;i <= n;++i)add(anc[i],i,0);

	dfs1(1,1);dfs2(1,1);

	for(int i = 1;i <= n;++i)f[i] = i;

	sort(es + 1,es + 1 + m,cmp_es);

	memset(ans,-1,sizeof(ans));

	for(int i = 1;i <= m;++i)

	{

		int u = es[i].u,v = es[i].v;

		if(d[u] - d[v] == es[i].w || d[v] - d[u] == es[i].w)continue;

		int en = LCA(u,v);

		u = find(u);v = find(v);

		while(dep[u] > dep[en])

		{

			ans[u] = d[es[i].u] + d[es[i].v] + es[i].w;

			f[u] = find(fa[u]);

			u = f[u];

		}

		while(dep[v] > dep[en])

		{

			ans[v] = d[es[i].u] + d[es[i].v] + es[i].w;

			f[v] = find(fa[v]);

			v = f[v];

		}

	}

	for(int i = 2;i <= n;++i)printf("%d\n",(ans[i] == -1 ? -1 : ans[i] - d[i]));

	return 0;

}