#include <fstream>
#include<queue>
#include<vector>
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
using namespace std;
int n,m,x,y,c,cost[50002],i;
vector<pair<int,int> > v[50002];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main ()
{ifstream f("dijkstra.in");
 ofstream g("dijkstra.out");
 f>>n>>m;
 while(m)
 {f>>x>>y>>c;
 v[x].pb(mp(c,y));
 
         m--;}
 cost[1]=-1;
 for(i=0;i<v[1].size();i++)
 q.push(v[1][i]);
 while(!q.empty())
 {if(!cost[q.top().second])
 {
 x=q.top().second;
 cost[x]=q.top().first;
 q.pop();
 for(i=0;i<v[x].size();i++)
 if(!cost[v[x][i].second]){
 v[x][i].first+=cost[x];
 q.push(v[x][i]);
 v[x][i].first-=cost[x];
 }
 }else
 q.pop();                
                  
                  }

for(i=2;i<=n;i++)
g<<cost[i]<<" ";
 f.close(); g.close();
return 0;
}