#include<fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long long inf=999999999,d[1300],q[1300],n,m;
struct graf{
int nod,cost;
graf *next;
};
graf *a[5000];

void add(int x,int y,int c){
graf *q=new graf;
q->nod=y;
q->cost=c;
q->next=a[x];
a[x]=q;
}

void citire(){
int i,j,x,y,c;
f>>n>>m;
for(i=1;i<=m;i++)      
f>>x>>y>>c,add(x,y,c);
}

void dijkstra()
{
for ( int i = 2; i <= n; ++i )
d[i] = inf;

long min, pmin = 1;
for ( i = 1; i <= n; ++i )
{
min = inf;

for ( int j = 1; j <= n; ++j )
if ( d[j] < min && !q[j] )
min = d[j], pmin = j;

q[pmin] = 1;

graf *t = a[pmin];


while ( t )
{
if( d[ t->nod ] > d[pmin] + t->cost )
d[ t->nod ] = d[pmin] + t->cost;

t = t->next;
}

}
}

void afis(){
int i;
for(i=2;i<=n;i++)
g<<d[i]<<' ';
g<<'\n';
}

int main(){
citire();
dijkstra();
afis();
g.close();
return 0;
}