#include <cstdio>
#include <vector>
#include <queue>
#define NMax 50002
#define INF 1e9

using namespace std;

int dist[NMax];
bool seen[NMax];
vector< pair<int,int> > v[NMax];
queue <int> Q;

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	int m, n;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		v[a].push_back(make_pair(b, c));
	}
	for(int i=1; i<=n; i++) dist[i]=INF;

	dist[1]=0;
	Q.push(1);
	while(!Q.empty())
	{
		int node = Q.front();
		Q.pop();
		seen[node]=0;
		vector< pair<int,int> > :: iterator it;
		for(it=v[node].begin(); it!=v[node].end(); it++)
		{
			int b = it -> first;
			int c = it -> second;
			if(dist[b] > dist[node]+c)
			{
				dist[b] = dist[node]+c;
				if(!seen[b])
				{
					seen[b]=1;
					Q.push(b);
				}
			}
		}
	}
	for(int i=2; i<=n; i++)
	{
		if(dist[i] == INF)
			dist[i] = 0;
		printf("%d ", dist[i]);
	}
}