#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void read();
void solve();
void check();
void print();

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;
const int oo = 0x3f3f3f;

int n, m;
int dist[MAX_NODES];
int inQueue[MAX_NODES];
vector<struct node *> List[MAX_NODES];

struct node
{
	int right;
	int cost;
	node(int a, int b) { right = a; cost = b; };
};

int main()
{
	read();
	solve();
	check();
	print();

	return 0;
}

void read()
{
	ifstream f("dijkstra.in", fstream::in);

	f >> n >> m;
	int left, right, cost;

	for (int i = 1; i <= m; ++i)
	{
		f >> left >> right >> cost;

		List[left].push_back(new node(right, cost));
	}

	f.close();
};

void solve()
{
	queue<int> Q;
	
	for (int i = 1; i <= n; ++i)
		dist[i] = oo;

	int start_node = 1;
	dist[start_node] = 0;
	Q.push(start_node);
	inQueue[start_node] = true;

	while (!Q.empty())
	{
		static int nod;
		nod = Q.front();
		Q.pop();
		inQueue[nod] = false;

		for (vector<struct node*>::iterator it = List[nod].begin(); it != List[nod].end(); it = it + 1)
			if (dist[(*it)->right] > dist[nod] + (*it)->cost)
			{
				dist[(*it)->right] = dist[nod] + (*it)->cost;
				if (!inQueue[(*it)->right])
				{
					Q.push((*it)->right);
					inQueue[(*it)->right] = true;
				}

			}
	}
};

void check()
{
};

void print()
{
	ofstream f("dijkstra.out", fstream::out);

	for (int i = 2; i <= n; ++i)
		f << dist[i] <<" ";
	f.close();
};