提交记录

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair <int, int> pii;

const int N = 100010, M = 400010;
const int inf = 0x3f3f3f3f;

int head[N], nxt[M], to[M], w[M], idx;

void init() {
	idx = 0;
	memset(head, -1, sizeof head);
}

void add(int a, int b, int c) {
	nxt[idx] = head[a], head[a] = idx;
	to[idx] = b, w[idx] = c, idx++;
}

int n, m, ans[N];
vector <pii> v[N];
int dist[N], prex[N], prew[N];
map <pii, bool> mp;
int dep[N], fa[N][20];
vector <int> tag[N];
multiset <int> se;
struct edge {
	int a, b, c;
} e[M];
struct node {
	int x, dis;
	bool operator < (const node &cmp) const {
		return dis > cmp.dis;
	}
};

void dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	priority_queue <node> q;
	q.push({1, 0});
	dist[1] = 0;
	while (!q.empty()) {
		node f = q.top(); q.pop();
		if (f.dis != dist[f.x]) continue;
		for (int i = head[f.x]; ~i; i = nxt[i]) {
			if (f.dis+w[i] < dist[to[i]]) {
				dist[to[i]] = f.dis+w[i];
				prex[to[i]] = f.x, prew[to[i]] = w[i];
				q.push({to[i], dist[to[i]]});
			}
		}
	}
}

void dfs_lca(int x, int p) {
	dep[x] = dep[p]+1;
	for (pii i : v[x]) {
		int to = i.x;
		fa[to][0] = x;
		for (int j = 1; j < 20; j++) {
			fa[to][j] = fa[fa[to][j-1]][j-1];
		}
		dfs_lca(to, x);
	}
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int i = 19; i >= 0; i--) {
		if (dep[fa[a][i]] >= dep[b]) {
			a = fa[a][i];
		}
	}
	if (a == b) return a;
	for (int i = 19; i >= 0; i--) {
		if (fa[a][i] != fa[b][i]) {
			a = fa[a][i], b = fa[b][i];
		}
	}
	return fa[a][0];
}

void dfs(int x) {
	ans[x] = *se.begin()-dist[x];
	for (int t : tag[x]) {
		if (t > 0) se.insert(t);
		else {
			multiset <int> :: iterator it;
			it = se.find(-t);
			se.erase(it);
		}
	}
	for (pii i : v[x]) {
		int to = i.x;
		dfs(to);
	}
	for (int t : tag[x]) {
		if (t > 0) {
			multiset <int> :: iterator it;
			it = se.find(t);
			se.erase(it);
		} else se.insert(-t);
	}
}

int main() {
//	freopen("data.in", "r", stdin);
	
	init();
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c), add(b, a, c);
		e[i] = {a, b, c};
	}
	
	dijkstra();
	
	for (int i = 2; i <= n; i++) {
		v[prex[i]].push_back({i, prew[i]});
		mp[{prex[i], i}] = mp[{i, prex[i]}] = true;
	}
	
	dfs_lca(1, 0);
	
	for (int i = 1; i <= m; i++) {
		int a = e[i].a, b = e[i].b, c = e[i].c;
		if (!mp[{a, b}]) {
			int p = lca(a, b);
			int d = dist[a]+dist[b]-dist[p]+c;
			tag[p].push_back(d);
			tag[a].push_back(-d);
			tag[b].push_back(-d);
		}
	}
	
	memset(ans, 0x3f, sizeof ans);
	se.insert(inf);
	dfs(1);
	
	for (int i = 2; i <= n; i++) {
		if (ans[i] >= 5e8) puts("-1");
		else printf("%d\n", ans[i]);
	}
	
	return 0;
}