//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define nr 50005
using namespace std;
using ll = long long int;
fstream f("dijkstra.in");
ofstream o("dijkstra.out");
int e, m;
vector<pair<int, int>> graf[nr];
bool vizitat[nr];
vector<int>cost(nr, INT_MAX);

struct cmp
{
	bool operator() (int x, int y)
	{
		return cost[x] > cost[y];
	}
};

priority_queue<int, vector<int>, cmp> coada;
void dijkstra(int start)
{
	coada.push(start);
	cost[start] = 0;
	vizitat[start] = true;
	while (!coada.empty())
	{
		int nod = coada.top();
		coada.pop();
		//	vizitat[nod] = false;
		for (size_t i = 0; i < graf[nod].size(); i++)
		{
			int vecin = graf[nod][i].first;
			int Cost = graf[nod][i].second;
			if (cost[nod] + Cost < cost[vecin])
			{
				cost[vecin] = cost[nod] + Cost;
				if (vizitat[vecin] == false)
				{
					coada.push(vecin);
					vizitat[vecin] = true;
				}
			}
		}
	}
}

int main()
{
	f >> e >> m;
	for (size_t i = 1; i <= m; i++)
	{
		int c, d, e;
		f >> c >> d >> e;
		graf[c].push_back({ d,e });
	}
	dijkstra(1);

	for (size_t i = 2; i <= e; i++)
	{
		if (cost[i] != INT_MAX)
		{
			o << cost[i] << " ";
		}
		else
		{
			o << "0 ";
		}
	}
}