#include #define ft first #define sc second #define lb lower_bound #define ub upper_bound #define pb push_back #define pt(sth) cout << sth << "\n" #define chmax(a, b) {if(ab) a=b;} #define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD using namespace std; typedef long long ll; typedef pair P; typedef map Map; static const ll INF=1e18; static const ll MAX=1e5+7; static const ll MOD=1e9+7; ll max(ll a, ll b) {return a>b ? a:b;} ll min(ll a, ll b) {return at=t; this->c=c; } }; ll N, M; vector g[MAX]; ll d[MAX][2]; void dijkstra(ll s) { ll u, i; ll clr[MAX][2]={}; for(i=0; i p, q; d[s][0]=0; p.push(P(0, s)); while(p.size() || q.size()) { P f, h; ll u; if(p.size()) { f=p.top(); p.pop(); u=f.sc; if(d[u][0]==-f.ft) { clr[u][0]=1; for(i=0; id[u][0]+e.c) { d[e.t][0]=d[u][0]+e.c; p.push(P(-d[e.t][0], e.t)); } if(clr[e.t][1]==0 && d[e.t][1]>d[u][0]) { d[e.t][1]=d[u][0]; q.push(P(-d[e.t][1], e.t)); } } } } if(q.size()) { h=q.top(); q.pop(); u=h.sc; if(d[u][1]==-h.ft) { clr[u][1]=1; for(i=0; id[u][1]+e.c) { d[e.t][1]=d[u][1]+e.c; q.push(P(-d[e.t][1], e.t)); } } } } } } int main(void) { ll i, j; cin >> N >> M; for(i=0; i> a >> b >> c; a--; b--; g[a].pb(Edge(b, c)); g[b].pb(Edge(a, c)); } dijkstra(0); for(i=0; i