#include <stdio.h>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

#define mp make_pair
#define NN 50008
#define MX 999999999;

using namespace std;

vector < pair <int,int>> a[NN];
vector < pair <int,int>>::iterator itt;

multiset <pair <int,int>> H;
multiset <pair <int,int>>::iterator it;
int d[NN],pre[NN],n,m,i,x,y,z,cost,x1,r,cr;

int main()
{
freopen("dijkstra.in", "r",stdin);
freopen("dijkstra.out", "w",stdout);

scanf("%d%d",&n,&m);
for(i=2;i<=n;i++)
d[i]=MX;

for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(mp(y,z));
}
H.insert(mp(1,0));
while (H.size()!=0){
 it=H.begin();
 cost=(*it).second;
 x1=(*it).first;
 for(itt=a[x1].begin();itt!=a[x1].end();++itt){
   r=(*itt).first;
   cr=(*itt).second;
  if (cost+cr<d[r]){d[r]=cost+cr;H.insert(mp(r,d[r]));pre[r]=x1;}
 }
H.erase(it);

}
for(i=2;i<=n;i++)printf("%d ",d[i]);
return 0;
}