#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct Edge
{
    int nod,cost;
};

int main()
{
    int n,m,i,inf;
    f>>n>>m;
    inf=(n-1)*20000;
    vector<vector<Edge>>G(n+1);
    vector<int>d(n+1,inf);
    set<pair<int,int>>Q;
    for(i=0; i<m; i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        Edge m;
        m.nod=b;m.cost=c;
        G[a].push_back(m);
    }
    d[1]=0;
    Q.insert(make_pair(0,1));
    while(!Q.empty())
    {
        int u=(*Q.begin()).second;
        Q.erase(Q.begin());
        for(auto v:G[u])
            if(d[v.nod]>d[u]+v.cost)
            {
                Q.erase(make_pair(d[v.nod],v.nod));
                d[v.nod]=d[u]+v.cost;
                Q.insert(make_pair(d[v.nod],v.nod));
            }
    }
    for(i=2; i<=n; i++)
    {
        if(d[i]==inf)
            d[i]=0;
        g<<d[i]<<" ";
    }
    return 0;
}