#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
const int NMAX=50005,INF=INT_MAX;
int n,m,dist[NMAX];
priority_queue < pair<int,int> > pq;
vector < pair<int,int> > G[NMAX];
bool viz[NMAX];
void citire(){
    int x,y,w;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>w;
        G[x].push_back(make_pair(-w,y));
    }
}
void dijkstra()
{
    for(int i=2;i<=n;i++) dist[i]=INF;
    dist[1]=0;
    pq.push(make_pair(0,1));
    while(!pq.empty())
    {
        int nod=pq.top().second;
        pq.pop();
        if(viz[nod]) continue;
        viz[nod]=true;
        for(int i=0;i<G[nod].size();i++)
        {
            int nodd=G[nod][i].second;
            int w=G[nod][i].first;
            if(dist[nodd]>dist[nod]-w)
            {
                dist[nodd]=dist[nod]-w;
                pq.push(make_pair(-dist[nodd],nodd));
            }
        }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(dist[i]==INF) fout<<"0 ";
    else fout<<dist[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}