#include<fstream>
#include<iostream>
using namespace std;
int maxim=100000;
int a[20000][20000],n,m;
int r;
int s[100000];
int d[100000];
int t[100000];
ofstream g("dijkstra.out");

void citire_cost()
{fstream f;
int i,j,x,y,c;
f.open("dijkstra.in",ios::in);

f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
a[i][j]=0;
else
a[i][j]=maxim;
for(i=1;i<=m;i++)
{f>>x>>y>>c;
a[x][y]=c;}}


void cauta_min(int &vf)
{int min=maxim;
for(int i=1;i<=n;i++)
if(s[i]==0)
if(d[i]<min){min=d[i];vf=i;}}

void imbunatatire_drum(int vf)
{for(int i=1;i<=n;i++)
if(s[i]==0)
if(d[i]>d[vf]+a[vf][i])
{d[i]=d[vf]+a[vf][i];
t[i]=vf;}}



int main()
{int vf;int i;
citire_cost();



for(i=1;i<=n;i++)
if(i!=1){d[i]=a[1][i];
if(a[1][i]!=maxim)t[i]=1;}
for(i=1;i<=n-1;i++)
{cauta_min(vf);s[vf]=1;imbunatatire_drum(vf);}

for(i=2;i<=n;i++)
if(i!=1){
g<<d[i]<<" ";}
return 0;}