#include<cstdio>
    #include<vector>
    #include<set>
    #define INF 50000002
    #define MAX 50001
    #define pb push_back
    using namespace std;
    int n , m  , d[MAX];
    bool inq[MAX];
    vector<int> g[MAX] , c[MAX];
    vector<int>::iterator it,it1;

    struct Compar{
    bool operator()(int i , int j)
    {
        return d[i] < d[j];
    }
    };

    multiset<int , Compar> Q;

    void citire();
    void dijkstra();
    void tipar();

    int main()
    {
        citire();
        dijkstra();
        tipar();
        return 0;
    }

    void citire()
    {
        int x,y,cost;
        freopen("dijkstra.in" , "r" , stdin );
        scanf("%d%d" , &n , &m );
        for( int i = 1 ; i <= m ; ++i )
        {
            scanf("%d%d%d" , &x , &y , &cost );
            g[x].pb(y);
            c[x].pb(cost);
        }
    }

    void dijkstra()
    {
        int k;
        for(int i = 1 ; i<= n ; ++i )d[i] = INF;
        d[1] = 0;
        Q.insert(1);
        while(!Q.empty())
        {
            k = *Q.begin();
            Q.erase(Q.begin());
            inq[k] = 0;
            for( it = g[k].begin(), it1 = c[k].begin() ; it != g[k].end() ; it++ , it1++)
            {
                if(d[*it] > d[k] + *it1)
                {
                    if(inq[*it])
                        Q.erase(*it);
                    else
                        inq[*it] = 1;
                    d[*it] = d[k] + *it1;
                    Q.insert(*it);
                }
            }

        }
    }

    void tipar()
    {
        freopen("dijkstra.out" , "w" , stdout );
        for( int i = 2 ; i<= n ; ++i )
        {
            if(d[i] == INF)
                printf("0 ");
            else
                printf("%d " , d[i]);
        }
    }