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

//Definitii
#define cost first
#define dest second

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

//Variabile
FILE *in, *out;

int nodes, edges;

vector<int> dist(sz, infinity);
vector<pair <int, int> > graph[sz];
vector<pair <int, int> >::iterator it, end;

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;

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

    fscanf(in,"%d%d",&nodes, &edges);

    for(int i=1; i<=edges; ++i)
    {
        int vFrom, vTo, vCost;
        fscanf(in,"%d%d%d",&vFrom, &vTo, &vCost);
        graph[vFrom].push_back(make_pair(vCost, vTo));
    }

    heap.push(make_pair(0, 1));
    dist[1] = 0;

    while(!heap.empty())
    {
        int current = heap.top().dest;
      /*  if(dist[current] != heap.top().first)
        {
            heap.pop();
            continue;
        }*/
        heap.pop();

        end = graph[current].end();

        for(it=graph[current].begin(); it!=end; ++it)
        {
            if(dist[current] + it->cost < dist[it->dest])
            {
                dist[it->dest] = dist[current] + it->cost;
                heap.push(make_pair(dist[it->dest], it->dest));
            }
        }

    }

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



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