// Dijkstra pe heapuri.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <limits>
#include <utility>
using namespace std;

#define INT_MAX 2147483647

const int INFINITE  = INT_MAX;
const int UNDEFINED = 0xFFFFFFFF;
const int START     = 1;

FILE *in  = fopen ("dijkstra.in",  "r");
FILE *out = fopen ("dijkstra.out", "w");

vector <pair<int, int> > muchii[50001];

int dist[50001];

struct cmp
{
    bool operator() (const int &i, const int &j)
    {
        return dist[i] > dist[j];
    }
};

int main(int argc, char* argv[])
{
    int i, n, m;
    fscanf (in, "%d%d", &n, &m);
	
    for (i = 1; i <= m; ++i)
    {
        int nod1, nod2, cost;
		fscanf(in, "%d%d%d", &nod1, &nod2, &cost);
		
        muchii[nod1].push_back(make_pair(nod2, cost));
    }
	
    priority_queue<int, vector<int>, cmp> myQueue;
    set<int> mySet;
	
    int visited[50001] = { 0 };
    int previous[50001];
	
    dist[START] = 0;
	for (i = 1; i <= n; ++i)
	{
		if (i != START)
		{
			dist[i]		= INFINITE;
			previous[i] = UNDEFINED;
		}
		//myQueue.push(i);
	}

	myQueue.push(START);
	while (!myQueue.empty())
	{
		int u = 1;
		do
		{			
			u = myQueue.top();
			myQueue.pop();

			if (visited[u] == 0)
				break;
		}
		while (visited[u] != 0);
		visited[u] = 1;

		for (vector<pair<int,int> >::iterator v = muchii[u].begin(); v != muchii[u].end(); ++v)
		{
			int nod = (*v).first;
			int len = (*v).second;

			int alt = dist[u] + len;
			if (alt < dist[nod])
			{			
				dist[nod]	  = alt;
				previous[nod] = u;
				myQueue.push(nod);
			}
		}
	}
    for (i = 2; i <= n; ++i)
        fprintf (out, "%d ", dist[i]);
	
    return 0;
}