#include <bits/stdc++.h>
#define Dmax 50005
#define inf 0x3F3F3F3F
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,dist[Dmax];
vector< pair< int, int> > G[Dmax];
struct Compare{

    bool operator()(int a, int b)
    {
        return dist[a] < dist[b];
    }

};
priority_queue <int, vector<int>, Compare> Q;


void Dijkstra(int start)
{
    for(int i = 1; i <= n; i++)
        dist[i] = inf;

    dist[start] = 0;
    Q.push(start);
    while(!Q.empty())
    {
        int nod = Q.top();
        Q.pop();
        for(vector<pair<int,int> >::iterator it = G[nod].begin(); it < G[nod].end(); it++)
        {
            int Next = it ->first;
            int Cost = it->second;
            if(dist[Next] > dist[nod] + Cost)
            {
                dist[Next] = dist[nod] + Cost;
                Q.push(Next);
            }

        }


    }




}

int main()
{
        f>>n>>m;
        for(int i = 1; i <= m; i++)
        {
            int x,y,c;
            f>>x>>y>>c;
            G[x].push_back({y,c});
        }

        Dijkstra(1);

        for(int i = 2; i <= n; i++)
            if(dist[i] == inf)
                g<<"0 ";
            else
                g<<dist[i]<<" ";

    return 0;
}