//#include <iostream>
#include <fstream>
#include<queue>
#include<utility>
using namespace std;
vector<pair< short,int> > v[50003];
priority_queue<pair< short,int> ,vector<pair<short,int> >,greater<pair<short,int > > > p;
int n,m,i,j,x,y,c,viz[50003],cost[50003];
int main ()
{
ifstream f("dijkstra.in");
f>>n>>m; 
for(i=1;i<=n;i++)
{v[i].push_back(make_pair(0,0));
cost[i]=2000000000;
}

for(i=1;i<=m;i++)
{f>>x>>y>>c;
v[x].push_back(make_pair(c,y));
v[x][0].second++;
}


viz[1]=1;

for(i=1;i<=v[1][0].second;i++)
{p.push(make_pair(v[1][i].first,v[1][i].second));
cost[v[1][i].second]=v[1][i].first;
}
for(j=1;j<n;j++)
{if(p.empty())break;
y=p.top().second;

p.pop();
if(!viz[y])
{
           for(i=1;i<=v[y][0].second;i++)
{
           if(!viz[v[y][i].second])
{p.push(v[y][i]); }
if(cost[v[y][i].second]>cost[y]+v[y][i].first)
cost[v[y][i].second]=v[y][i].first+cost[y];
}
viz[y]=1;}
}
ofstream g("dijkstra.out");
for(i=2;i<=n;i++)
if(cost[i]==2000000000)
g<<0<<" ";
else
g<<cost[i]<<" ";
 f.close(); g.close();
return 0;
}