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

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

struct Edge
{
    int nod,cost;
    Edge(int n,int c)
    {
        nod=n;
        cost=c;
    }
};

int main()
{
    int n,m,i,a,b,c,inf;
    f>>n>>m;
    inf=(n-1)*20000;
    vector<vector<Edge>>G(n+1);
    vector<int>distance(n+1,inf);
    set<pair<int,int>>Q;

    for(i=0; i<m; i++)
    {
        f>>a>>b>>c;
        G[a].push_back(Edge(b,c));
    }

    distance[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(distance[v.nod]>distance[u]+v.cost)
            {
                Q.erase(make_pair(distance[v.nod],v.nod));
                distance[v.nod]=distance[u]+v.cost;
                Q.insert(make_pair(distance[v.nod],v.nod));
            }
    }

    for(i=2; i<=n; i++)
    {
        if(distance[i]==inf)
            distance[i]=0;
        g<<distance[i]<<" ";
    }

    return 0;
}