#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M, x, y, c, D[maxn];
struct muchii{ int x, c;};
struct cmp
{
    bool operator()( const int &a, const int &b )const
    {
        if (D[a]>D[b]) return 1;
        return 0;
    }
};

vector < muchii > v[maxn];
priority_queue < int , vector < int > , cmp > Q;

int main()
{
    f>>N>>M;
    muchii aux;
    for (int i=1; i<=M; ++i)
    {
        f>>x>>aux.x>>aux.c;
        v[x].push_back(aux);
    }

    memset (D, inf, sizeof(D));
    D[1]=0; Q.push(1);

    vector < muchii > :: iterator it, final;

    while ( Q.size() )
    {
        x=Q.top(); Q.pop();
        it=v[x].begin(); final=v[x].end();

        for ( ; it!=final; ++it)
        {
            if (D[x]+it->c<D[it->x])
                D[it->x]=D[x]+it->c, Q.push(it->x);
        }
    }

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