#include <iostream>
#include <fstream>
#define f first
#define s second
#include <vector>
#include <queue>
#define pinf 1000000007
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector < pair<int, int> > v[50010];
priority_queue < pair<int, int>, vector< pair<int, int> >, greater < pair<int, int> > > q;
int n,m,i,x,y,c,d[50010],viz[50010];
pair<int,int>aux;
void dijkstra(int st)
{
viz[st]=1;
for(int j=0;j<v[st].size();j++)
{
d[v[st][j].s]=v[st][j].f;
q.push(v[st][j]);
}
for(int i=1;i<n&&!q.empty();i++)
{
while(viz[q.top().s]!=0&&!q.empty())
{
q.pop();
}
if(!q.empty())
{
aux=q.top();
q.pop();
}
viz[aux.s]=1;
for(int j=0;j<v[aux.s].size();j++)
{
if(viz[v[aux.s][j].s]==0)
{
if(d[v[aux.s][j].s]>d[aux.s]+v[aux.s][j].f)
{
d[v[aux.s][j].s]=d[aux.s]+v[aux.s][j].f;
q.push(make_pair(d[v[aux.s][j].s],v[aux.s][j].s));
}
}
}
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y>>c;
v[x].push_back(make_pair(c,y));
}
for(i=1;i<=n;i++)
{
d[i]=pinf;
}
dijkstra(1);
for(i=2;i<=n;i++)
{
if(d[i]==pinf)
{
fout<<0<<" ";
}
else
{
fout<<d[i]<<" ";
}
}
return 0;
}