#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Edge
{
    int nod, cost;
};
int main()
{
    int N, M;
    f>>N>>M;
    Edge edge;

    vector<int>d(N, (N-1)*20000), viz(N, 0);
    d[1]=0;
    int ind;
    vector<vector<Edge> >G(N);
    for(int i=1; i<=N; i++)
    {
        int a, b, cost;
        f>>a>>b>>cost;
        edge.nod=b;
        edge.cost=cost;
        G[a].push_back(edge);
    }

    for(int i=1; i<=N; i++)
    {
        int minim=(N-1)*20000, ind=-1;
        for(int j=0; j<N; j++)
            if(d[j]<minim && viz[j]==0)
            {
                minim=d[j];
                ind = j;
            }
        if(ind==-1)
            break;

        for(auto edge: G[ind])
        {
            if(d[edge.nod]>d[ind]+edge.cost)
                d[edge.nod]=d[ind]+edge.cost;

            viz[ind]=1;
        }
    }
    for(int i=1; i<=N; i++)
        g<<d[i]<<" ";
}