#include #define INF 2147483647 #define INF_LL 9223372036854775807 #define MOD 1000000007 using namespace std; typedef long long int ll; typedef unsigned long long int ull; struct edge { ll to; ll cost; }; // d v f typedef pair> P; int main() { int N, M; cin >> N >> M; vector> G(N, vector()); for (int i = 0; i < M; i++) { ll a, b, c; cin >> a >> b >> c; a--; b--; G[a].push_back({ b,c }); G[b].push_back({ a,c }); } vector d1(N, INF), d2(N, INF); priority_queue, greater

> q; d1[0] = 0; d2[0] = 0; q.push(P{ 0,{0,false} }); while (!q.empty()) { P p = q.top(); q.pop(); ll v = p.second.first; for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (p.second.second == false) { if (d1[e.to] > p.first + e.cost) { d1[e.to] = p.first + e.cost; q.push(P{ d1[e.to],{ e.to, p.second.second } }); } if (d1[e.to] > p.first) { d1[e.to] = p.first; q.push(P{ d1[e.to],{ e.to, true } }); } } if (d1[e.to] > d1[v] + e.cost) { d1[e.to] = d1[v] + e.cost; q.push(P{ d1[e.to], { e.to, p.second.second } }); } } } q.push(P{ 0,{ 0,true } }); while (!q.empty()) { P p = q.top(); q.pop(); ll v = p.second.first; if (d2[v] < p.first)continue; for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d2[e.to] > d2[v] + e.cost) { d2[e.to] = d2[v] + e.cost; q.push(P{ d1[e.to],{ e.to, p.second.second } }); } if (p.second.second == false) { if (d2[e.to] > d2[v]) { d2[e.to] = d2[v]; q.push(P{ d2[e.to],{ e.to, true } }); } } } } for (int i = 0; i < N; i++) { //cout << d1[i] << " " << d2[i] << endl; cout << d1[i] + d2[i] << endl; } }