//vila-campion
/*#include<bits/stdc++.h>
using namespace std;
deque < pair<int,int> > Min,Max;
int ans;
int main()
{
int n,k,i,x;
ifstream fin("vila2.in");
ofstream fout("vila2.out");
fin>>n>>k;
for(i=1;i<=k;i++)
{
fin>>x;
while(!Max.empty() && Max.back().first<=x )
Max.pop_back();
Max.push_back(make_pair(x,i));
while(!Min.empty() && Min.back().first>=x )
Min.pop_back();
Min.push_back(make_pair(x,i));
}
ans=Max.front().first-Min.front().first;
//cout<<ans;
for(i=k+1;i<=n;i++)
{
fin>>x;
if(Max.front().second<i-k)
Max.pop_front();
if(Min.front().second<i-k)
Min.pop_front();
while(!Max.empty() && Max.back().first<=x )
Max.pop_back();
Max.push_back(make_pair(x,i));
while(!Min.empty() && Min.back().first>=x )
Min.pop_back();
Min.push_back(make_pair(x,i));
ans=max(ans,Max.front().first-Min.front().first);
}
fout<<ans;
fin.close();
fout.close();
}*/
//deque-infoarena
/*#include<stdio.h>
int D[5000010],A[5000010];
unsigned long long s;
//creez un deque in care retin pozitiile sirului T[i], in care T[i1] este minimul cautat
int main()
{
int i,n,k,p=1,u=0,x;
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d %d",&n,&k);
for(i=1;i<=k;i++)
{ scanf("%d ",&A[i] );
//cout<<A[i];
while(p<=u && A[D[u]]>A[i])
u--;
D[++u]=i;
}
s+=A[D[p]];
//printf("%d",s);
for(i=k+1;i<=n;i++)
{
scanf("%d ",&A[i] );
if(D[p]==i-k) p++;
while(p<=u && A[D[u]]>A[i])
u--;
D[++u]=i;
s+=A[D[p]];
}
printf("%d",s);
}*/
/*#include<bits/stdc++.h>
using namespace std;
deque < pair<int,int> > Min;
long long ans;
int main()
{
int n,k,i,x;
ifstream fin("deque.in");
ofstream fout("deque.out");
fin>>n>>k;
for(i=1;i<=k;i++)
{
fin>>x;
while(!Min.empty() && Min.back().first>=x )
Min.pop_back();
Min.push_back(make_pair(x,i));
}
ans=Min.front().first;
//cout<<ans;
for(i=k+1;i<=n;i++)
{
fin>>x;
if(Min.front().second==i-k)
Min.pop_front();
while(!Min.empty() && Min.back().first>=x )
Min.pop_back();
Min.push_back(make_pair(x,i));
ans+=Min.front().first;
}
fout<<ans;
fin.close();
fout.close();
}*/
/*#include<iostream>
#include<fstream>
using namespace std;
int n,tata[100001],h[100001],m;
void Union_ponderare(int x,int y)
{
if(h[x]>h[y]) tata[y]=x;
else
{
tata[x]=y;
if(h[x]==h[y]) h[y]++;
}
}
int Find_compresie(int x)
{
int r=x,y=x,help;
while(tata[r]!=r) r=tata[r];
while(y!=r)
{
help=tata[y];
tata[y]=r;
y=help;
}
return r;
}
int main()
{
int i,c,x,y;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
fin>>n>>m;
for(i=1;i<=n;i++)
{tata[i]=i;
h[i]=1;
}
for(i=1;i<=m;i++)
{
fin>>c;
if(c==1)
{
fin>>x>>y;
if(Find_compresie(x)!=Find_compresie(y))
Union_ponderare(Find_compresie(x),Find_compresie(y));
}
else
{
fin>>x>>y;
if(Find_compresie(x)==Find_compresie(y))
fout<<"DA"<<'\n';
else fout<<"NU"<<'\n';
}
}
}*/
#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream gout("dijkstra.out");
const int NMax=50052;
const int Dim=(1<<30);
typedef struct LM{int nod,cost;};
int d[NMax];
int n,m;
vector <int> G[NMax], C[NMax];
typedef struct cmpdst
{
bool operator() (LM x, LM y)
{
return x.cost>y.cost;
}
};
priority_queue <LM, vector<LM> , cmpdst> q;
void citire()
{ int i,x,y,z;
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>x>>y>>z;
G[x].push_back(y);
C[x].push_back(z);
}
}
void dijkstra(int S)
{ int viz[NMax]={0},i;
for(i=1;i<=n;i++)
d[i]=Dim;
d[S]=0;
LM aux,aux2;
aux.cost=0;
aux.nod=S;
q.push(aux);
while(!q.empty())
{
aux=q.top();
q.pop();
if(viz[aux.nod]==1);
else
{
viz[aux.nod]=1;
for(i=0;i<G[aux.nod].size();i++)
{
int halp;
halp=G[aux.nod][i];
if(!viz[halp])
{if(d[halp]>d[aux.nod]+C[aux.nod][i])
{
d[halp]=d[aux.nod]+C[aux.nod][i];
aux2.nod=halp;
aux2.cost=d[halp];
//if(!viz[aux2.nod])
q.push(aux2);
}
}
}
}
}
}
void afisare()
{
int i;
for(i=2;i<=n;i++)
if(d[i]!=Dim) gout<<d[i]<<' ';
else gout<<"0 ";
}
int main()
{
citire();
dijkstra(1);
afisare();
}