#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int M,N;
int lung[50005],v[50005],poz[50005]; // v=heap-ul

struct elem
{
    int d,val;
};
vector<elem> a[50005];

inline int firstson(int);
inline int secondson(int);
inline int dad(int);
inline void percolate(int);
inline void sift(int);
inline void inser(int);

int main()
{
    f>>N>>M;
    int copN=N;
    while (M--)
    {
        int x,y,val;
        f>>x>>y>>val;
        elem A;
        A.d=y;
        A.val=val;
        a[x].pb(A);
    }
    FOR (i,2,N) {
        lung[i]=259999999;
        poz[i]=-1;
    }
    lung[1]=0;
    poz[1]=1;
    v[1]=1;
    /*FOR (i,1,copN)
        cout<<v[i]<<' ';
    cout<<'\n';
    FOR (i,1,copN)
        cout<<lung[i]<<' ';
    cout<<"\n\n";*/
    N=1;
    while (N)
    {
        int x=v[1];
        swap(v[1],v[N]);
        poz[v[1]]=1;
        N--;
        sift(1);
        for (unsigned int j=0;j<a[x].size();++j) {
            if (lung[a[x][j].d]>lung[x]+a[x][j].val) {
                lung[a[x][j].d]=lung[x]+a[x][j].val;
                if (poz[a[x][j].d]==-1) {
                    v[++N]=a[x][j].d;
                    poz[a[x][j].d]=N;
                    percolate(N);
                }
                else
                    percolate( poz[a[x][j].d] );
                /*else
                    sift( poz[a[x][j].d] );*/
            }
        }
        /*FOR (i,1,copN)
            cout<<v[i]<<' ';
        cout<<'\n';
        FOR (i,1,copN)
            cout<<poz[i]<<' ';
        cout<<'\n';
        FOR (i,1,copN)
            cout<<lung[i]<<' ';
        cout<<"\n\n";*/
    }
    FOR (i,2,copN)
        if (lung[i]==259999999)
            g<<0<<' ';
        else
            g<<lung[i]<<' ';
    f.close();g.close();
    return 0;
}


inline int firstson(int n)
{
    return 2*n;
}

inline int secondson(int n)
{
    return 2*n+1;
}

inline int dad(int n)
{
    return n/2;
}

inline void percolate(int n)
{
    int val=v[n];
    while (n>1 && lung[val]<lung[v[dad(n)]])
    {
        swap(poz[v[n]],poz[v[dad(n)]]);
        swap(v[n],v[dad(n)]);
        n=dad(n);
    }
}

inline void sift(int n)
{
    int son;
    do {
        son=0;
        if (firstson(n)<=N)
        {
            son=firstson(n);
            if (secondson(n)<=N && lung[v[secondson(n)]]<lung[v[firstson(n)]])
                son=secondson(n);
            if (lung[v[son]]>=lung[v[n]])
                son=0;
        }
        if (son) {
            swap(poz[v[son]],poz[v[n]]);
            swap(v[son],v[n]);
            n=son;
        }
    }
    while (son);
}