#include <bits/stdc++.h>

using namespace std;
string prob="dijkstra";
ifstream in(prob+".in");
ofstream out(prob+".out");
vector< vector< pair<int,int> > > v(50001);
vector<int> dist(50001);
vector<bool> b(50001);
priority_queue<pair<int,int>> q;
void dij(){
    q.push({0,1});
    while(!q.empty()){
        pair<int,int> n=q.top();
        cout<<n.first<<" "<<n.second<<"\n";
        q.pop();
        int ff=n.second;
        if(b[ff])continue;
        b[ff]=1;
        for(auto i:v[ff]){
            int f=i.first;
            int s=i.second;
            q.push(make_pair(s,f));
            if(dist[f]>dist[ff]-s||dist[f]==0){
                dist[f]=dist[ff]-s;
            }
        }
    }
}
int main(){
    int n,m;
    in>>n>>m;
    for(;m;m--){
        int a,b,c;
        in>>a>>b>>c;
        v[a].push_back(make_pair(b,-c));
    }
    dij();
    for(int i=2;i<=n;i++)out<<dist[i]<<" ";

}