#include <bits/stdc++.h>
#define Dim 50002
#define oo 1e9
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N,M,D[Dim],T[Dim];
bool viz[Dim];

vector < pair<int,int> > V[Dim];

bool Bellman_Ford()
{
    for(int i=1;i<=N;i++)  D[i]=oo,T[i]=0;

    D[1]=0,T[1]=0;

    for(int i=1;i<=N-1;i++)
        for(int nod=1;nod<=N;nod++)
        for(unsigned int j=0;j<V[nod].size();j++)
        {
            int vecin=V[nod][j].first;
            int cost=V[nod][j].second;
            if( D[vecin] > D[nod] + cost )
            {
                D[vecin]=D[nod]+cost;
                T[vecin]=nod;
            }
        }

    for(int nod=1;nod<=N;nod++)
        for(unsigned int j=0;j<V[nod].size();j++)
            {
                int vecin=V[nod][j].first;
                int cost=V[nod][j].second;
                if( D[vecin] > D[nod] + cost ) return false;
            }
    return true;
}

int main()
{
    int a,b,c;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>a>>b>>c;;
        V[a].push_back({b,c});
    }
Bellman_Ford();

    for(int i=2;i<=N;i++)
    if(D[i]!=oo)g<<D[i]<<' ';
    else g<<0<<' ';

    return 0;
}