#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define INF 0x3f3f3f3f
int n, m;
vector< pair<int, int> > a[250001];
queue<int> Q;
bool s[250001];
int d[250001];

void Read();
void Dijkstra();
void Write();

int main()
{
	Read();
	Dijkstra();
	Write();
	return 0;
}

void Read()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	
	int x, y, z;
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> z;
		a[x].push_back(make_pair(y, z));
	}
	fin.close();
}
		
void Dijkstra()
{
	for(int i = 2; i <= n; ++i) 
		d[i] = INF;
	
	Q.push(1);
	
	while(!Q.empty())
	{
		int x = Q.front();
		for(int i = 0; i < (int)a[x].size(); ++i)
		{
			int nod = a[x][i].first;
			int cost = a[x][i].second;
			if( d[nod] > d[x] + cost)
			{
				d[nod] = d[x] + cost;
				Q.push(nod);
			}
		}
		Q.pop();
	}
}

void Write()
{
	ofstream fout("dijkstra.out");
	for(int i = 2; i <= n; ++i)
		if( d[i] != INF )
			fout << d[i] << " ";
		else
			fout << 0 << " ";
	fout.close();
}