#include <fstream>
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

vector< pair<int, int> > adj[50000];
int n, m;

void read()
{
	ifstream fin("dijkstra.in");
	int x, y, w;
	
	fin >> n >> m;
	
	for(int i = 1; i <= n; i++)
	{
		fin >> x >> y >> w;
		adj[x].push_back(make_pair(y, w));
	}
	
	fin.close();
}

int dist[50000];

void bellman_ford(int r)
{
	for(int i = 1; i <= n; i++)
		dist[i] = INT_MAX;
	
	dist[r] = 0;
	
	for(int i = 1; i <= n-1; i++)
		for(int j = 1; j <= n; j++)
			for(pair<int, int> p : adj[j])
			{
				int a = j, b = p.first, w = p.second;				
				
				dist[b] = min(dist[b], dist[a] + w);
			}
}

int main()
{
	read();
	
	bellman_ford(1);
	
	ofstream fout("dijkstra.out");
	
	for(int i = 2; i <= n; i++)
		fout << dist[i] << " ";
	
	fout.close();
	
	return 0;
}