#include<cstdio>
    #include<vector>
    #include<set>
    using namespace std;
    #define NMAX 50001
    #define INF 50000001
    #define pb push_back
    int N , M  , d[NMAX];
    struct comp{
        bool operator()(int a,int b)
        {
            return d[a] < d[b];
        }
    };
    vector<int> G[NMAX] , C[NMAX];
    multiset<int,comp> Q;

    void read();
    void dijkstra();
    void write();

    int main()
    {
        read();
        dijkstra();
        write();
        return 0;
    }

    void read()
    {
        int x , y , c;
        freopen("dijkstra.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for(int i = 1 ; i <= M; ++i)
        {
            scanf("%d%d%d" , &x , &y , &c );
            G[x].pb(y);
            C[x].pb(c);
        }
    }

    void dijkstra()
    {
        int nod;
        for(int i = 1 ; i<= N ; ++i)
            d[i] = INF;
        d[1] = 0;
        Q.insert(1);
        while(!Q.empty())
        {
            nod = *Q.begin();
            Q.erase(Q.begin());
            for(int i = 0 ; i <(int)G[nod].size() ; ++i )
                if(d[nod] + C[nod][i] < d[G[nod][i]])
            {
                d[G[nod][i]] = d[nod] + C[nod][i];
                Q.insert(G[nod][i]);
            }
        }
    }

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