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

using namespace std;


const int inf=1 << 30;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,s[500],p[500],d[500];



struct graf
{
	int nod,cost;
	graf *urm;
	
};

graf *W[50001];


void add(int x, int y, int z)

{
	graf *q;

q = new graf;
q->nod = y;
q->cost = z;
q->urm = W[x];
W[x] = q;

}


void citire()

{

f>>n>>m;;


int x, y, z;

for ( int i = 1; i <= m; ++i )

{
f>>x>>y>>z;
add(x, y, z);
}

}


void dijkstra()
{
	int i,j,min,y=0;
	
	//s[x]=1;
	
	
	for(i=2;i<=n;i++)
	{
		d[i]=inf;
		
	}
	
		
	for(i=1;i<=n;i++)
	{min=inf;
		for(j=1;j<=n;j++)
		
			if(!s[j] && d[j]<min)
			{
				min=d[j],y=j;
			}
			s[y]=1;
			graf *t=W[y];
			
			while(t)
			{cout<<"~!!";
				
				if(d[t->nod]>d[y]+t->cost)
					d[ t->nod ] = d[y] + t->cost;
				t=t->urm;
				
			}
			
			
			
		
	}
	
	
	
	
}



int main()
{
	

	
 int i;
	
	
	citire();	
	dijkstra();
	
	for(i=1;i<=n;i++)
		g<<d[i]<<" ";
	
return 0;
}