#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

multimap <int, int> v;
multimap <int, int>::iterator it;

struct TEdge
{
	int Dest, Weight;
};

vector <TEdge> Edges[50000];
char Visited[50000];
int d[50000],pre[50000];

FILE * fin;
FILE * fout;

int n,m;

//------------------------------------------------------
void citire()
{
	fin = fopen("dijkstra.in","r");
	fout= fopen("dijkstra.out","w");
	
	fscanf(fin,"%d %d",&n,&m);
	
	int i,j,a;
	TEdge b;
	for (i=1; i<=m; i++)
	{
		fscanf(fin,"%d %d %d",&a,&b.Dest,&b.Weight);
		
		Edges[a].push_back(b);
	}
		
	fclose(fin);
}
//------------------------------------------------------
void solve()
{
	
	int Node=1,i,j,Dest,Cost;
	d[Node]=1;
	
	for (i=1; i<n; i++)
	{
		Visited[Node]=1;		
		for (j=0; j<Edges[Node].size(); j++)
		{
			Dest=Edges[Node][j].Dest;
			Cost=d[Node]+Edges[Node][j].Weight;
			if ((Cost<d[Dest]) || (d[Dest]==0))
			{
				if (Visited[Dest] == 0) 
					if  (d[Dest]!=0)
					{
						it = v.find(d[Dest]);
						while (it->second != Dest) it++;
						
						v.erase(it);
						
						v.insert(pair<int,int>(Cost,Dest));
					} else
					{
						v.insert(pair<int,int>(Cost,Dest));
					}
				d[Dest]=Cost;
				pre[Dest]=Node;
			}
		}
		it=v.begin();		
		Node=it->second;
		
		v.erase(it);
	}
}
//------------------------------------------------------
int main()
{
	
	citire();
	solve();
	
	int i;
	for (i=2; i<=n; i++)
	{
		fprintf(fout,"%d ",d[i]-1);
	}
	
	fclose(fout);
	
	return 0;
}