#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAXN 50001
#define input_file "dijkstra.in"
#define output_file "dijkstra.out"
const int INF = 1 << 30;

vector< pair<int,int> > g[MAXN];
vector<int> d, color;
int n, m;

void read_graph()
{
	ifstream in(input_file, istream::in);
	int x, y, cost;
	in >> n >> m;
	for(int i = 0; i < m; i++)
	{
		in >> x >> y >> cost;
		g[x-1].push_back( make_pair(y-1, cost) );
	}
	in.close();
}

class mycomparator
{
public:
	bool operator() (const pair<int,int> &a,const pair<int,int> &b ) const
	{
		return (a.second > b.second);
	}
};

void dijkstra(int s)
{
	priority_queue< pair<int, int>, vector<pair<int,int> >, mycomparator> Q;
	color[s] = 1;
	d.assign(n, INF);
	d[s] = 0;
	for(int i = 0; i < (int) g[s].size(); i++)
	{
		d[ g[s][i].first ] = g[s][i].second;
		Q.push( g[s][i] );
	}
	while( !Q.empty() )
	{
		int u = Q.top().first; Q.pop();
		color[u] = 1;
		for(int i = 0; i < (int) g[u].size(); i++)
		{
			int v = g[u][i].first;
			if( color[v] == 1 ) continue; 
			int cost = g[u][i].second;
			if( d[u] + cost < d[v] )
			{
				d[v] = cost + d[u];
				Q.push( make_pair(v, d[v]) );
			}
		}
	}
}

void print_sol(int source)
{
	ofstream out(output_file, istream::out);
	for(int i = 0; i < n; i++)
	{
		if( i == source ) continue;
		(d[i] == INF) ? out << "0 ": out << d[i] << " ";
	}
	out << "\n";
	out.close();
}

int main()
{
	read_graph();
	color.assign(n,0);
	dijkstra(0);
	print_sol(0);
	return 0;
}