//Include
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

FILE *in, *out;

//Constante
const int sz = (int)5e4+1;
const int infinity = (1<<30)-1;

//Definitii
#define pb push_back
#define mp make_pair
#define pere pair<int, int>
#define cost first
#define node second

//Variabile
int nodes, edges;
int dist[sz];

vector <pere> graph[sz];
priority_queue <pere, vector<pere>, greater<pere> > pq;

//Main
int main()
{
	in=fopen("dijkstra.in", "rt");
	out=fopen("dijkstra.out", "wt");

    fscanf(in,"%d%d", &nodes, &edges);
    for(int i=2; i<=nodes; ++i)
        dist[i] = infinity;

    while(edges--)
    {
        int from, to, cost;
        fscanf(in,"%d%d%d", &from, &to, &cost);
        graph[from].pb(mp(cost, to));
    }
    pq.push(mp(0, 1));

    while(!pq.empty())
    {
        int currentNode = pq.top().node;
        pq.pop();

        vector <pere>::iterator it, end = graph[currentNode].end();
        for(it = graph[currentNode].begin(); it!=end; ++it)
            if(dist[currentNode] + it->cost < dist[it->node])
            {
                dist[it->node] = dist[currentNode] + it->cost;
                pq.push(mp(dist[it->node], it->node));
            }
    }

    for(int i=2; i<=nodes; ++i)
        fprintf(out,"%d ", (dist[i] == infinity) ? '0': dist[i]);
    fprintf(out,"\n");


	fclose(in);
	fclose(out);
	return 0;
}