//90 disjtra ultimul test TLE
#include<fstream>
#include<cstdio>
#include<queue>
using namespace std;
vector<pair< int,int> > v[50003];
FILE *f;
priority_queue<pair< int,int> ,vector<pair<int,int> >,greater<pair<int,int > > > p;
unsigned int n,m,i,j,x,y,cost[50003],c;
bool viz[50003];

int main ()
{f=fopen("dijkstra.in","r");

fscanf(f,"%d %d",&n,&m);
for(i=1;i<=n;i++)
{
cost[i]=2000000000;
}

for(i=1;i<=m;i++)
{fscanf(f,"%d %d %d",&x,&y,&c);
v[x].push_back(make_pair(c,y));
}
fclose(f);

viz[1]=true;


for(i=0;i<v[1].size();i++)
{                p.push(v[1][i]);
                 cost[v[1][i].second]=v[1][i].first;
                 
}

while(true)
{               if(p.empty())break;
                y=p.top().second;
                p.pop();
               
                 for(i=0;i<v[y].size();i++)
                 {
                  if(cost[v[y][i].second]>cost[y]+v[y][i].first)
                               {cost[v[y][i].second]=v[y][i].first+cost[y];
                               if(viz[v[y][i].second]==false)
                               {v[y][i].first+=cost[y];
                               p.push(v[y][i]);
                               } 
                             
                               }
                 }
                  viz[y]=true; 
                 
}
ofstream g("dijkstra.out");
for(i=2;i<=n;i++)
if(cost[i]==2000000000)
g<<0<<" ";
else
g<<cost[i]<<" ";
 g.close();
return 0;
}