//#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],spa[50003],tati[50003];
void dfs(int nod)
{tati[nod]=1;
for(int k=0;k<spa[nod];k++)
if(!tati[v[nod][k].second])
dfs(v[nod][k].second);
}int main ()
{
ifstream f("dijkstra.in");
f>>n>>m; 
for(i=1;i<=n;i++)
{
cost[i]=2000000000;
}

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


viz[1]=1;
dfs(1);
c=n;
for(i=2;i<=n;i++)
if(!tati[i]) {c--; cost[i]=0;}
c--;
for(i=0;i<spa[1];i++)
{                p.push(v[1][i]);
                 cost[v[1][i].second]=v[1][i].first;
                 
}

while(c)
{               if(p.empty())break;
                y=p.top().second;
                p.pop();
                if(!viz[y])
                {
                 for(i=0;i<spa[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];
                               p.push(make_pair(cost[v[y][i].second],v[y][i].second)); 
                             
                               }
                 }
                  viz[y]=1; c--;
                 }
}
ofstream g("dijkstra.out");
for(i=2;i<=n;i++)
g<<cost[i]<<" ";
 f.close(); g.close();
return 0;
}