#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define pb push_back

const int oo = 0x3f3f3f3f;

queue <int> Q;

const int N =5e4 + 17;

int D[N];

vector <pair <int, int> > v[N];

void Dijkstra()
{
	Q.push(1);
	while(!Q.empty())
	{
		int nod = Q.front();
		Q.pop();
		for(int i = 0; i < v[nod].size(); i++)
			if(D[nod] + v[nod][i].second < D[v[nod][i].first])
				D[v[nod][i].first] = D[nod] + v[nod][i].second, Q.push(v[nod][i].first);
	}
}

int main()
{
	int n, m;
	f >> n >> m;
	while(m--)
	{
		int x, y, c;
		f >> x >> y >> c;
		v[x].pb({y, c});
	}
	for(int i = 2; i <= n; i++)
		D[i] = oo;
	Dijkstra();
	for(int i = 2; i <= n; i++)
		g << D[i] << ' ';
}