#include <fstream>
#include <vector>
#include <queue>
#define NM 50006
#define inf 1e9
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,x,y,v;
int d[NM],fr[NM];
vector < pair < int, int > > a[NM];
priority_queue < pair < int, int > > q;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>v; a[x].push_back( make_pair(-v,y) );
    }
    q.push(make_pair(0,1));
    for(i=2;i<=n;i++){
        d[i]=-inf;
        q.push(make_pair(-inf,i));
    }
    while(!q.empty()){
        if(fr[q.top().second]==0){
            x=q.top().second;
            for(i=0;i<a[x].size();i++){
                if(a[x][i].first+d[x]>d[a[x][i].second]) { q.push(make_pair(a[x][i].first+d[x],a[x][i].second)); d[a[x][i].second]=a[x][i].first+d[x]; }
            }
            fr[x]++;
        } else q.pop();
    }
    for(i=2;i<=n;i++){
        if(d[i]!=-inf) g<<-d[i]<<' ';
          else         g<<0<<' ';
    }
    return 0;
}