#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;
 

#ifndef TEST
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
 
#define MAXN 50000

typedef long long ll;
typedef pair<int,int> pp;

int n,m;

vector<pp> a[MAXN];
int d[MAXN];

void Dijkstra(int origin)
{	
	char *seen;
	seen=new char[n];

	queue<int> tovisit;
	tovisit.push(origin);

	for (int i=0; i<n; i++)
		{
			seen[i]=0;
			d[i]=-1;
		}
	d[origin]=0;

	while (!tovisit.empty())
	{
		int t;
		t=tovisit.front();
		tovisit.pop();
		seen[t]=2;

		for (int i=0; i<a[t].size(); i++)
			if ((seen[a[t][i].first]!=2))
			{
				if (seen[a[t][i].first]==0) tovisit.push(a[t][i].first);
				seen[a[t][i].first]=1;
				d[a[t][i].first]=(d[a[t][i].first]==-1)?a[t][i].second +d[t]:(min(a[t][i].second +d[t],d[a[t][i].first]));
			}
	}
}

int main()
{
	fin>>n>>m;

	for (int i=0; i<m; i++)
	{
		int x,y,z;
		fin>>x>>y>>z;
		x--;
		y--;
		a[x].push_back( make_pair(y,z));
	}

	Dijkstra(0);

	for (int i=1; i<n; i++)
		if (d[i]+1) fout<<d[i]<<' ';
		else fout<<"0 ";

    return 0;
}