#include <fstream>
#include <queue>
#include <vector>
#define N 50005
#define INF 100000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n, m;
int noduri[N];
bool fol[N];
vector<pair<int, int> > graf[N];
struct comp{
     bool operator()(int x, int y){
         return noduri[x] > noduri[y];
     }
 };
 priority_queue<int, vector <int>, comp> coada;
 void dijkstra(int nod_start){
     for(int i = 1; i <= n; ++i)
         noduri[i] = INF;
     noduri[nod_start] = 0;
     coada.push(nod_start);
     fol[nod_start] = 1;
     while(!coada.empty()){
         int nod = coada.top();
         coada.pop();
         fol[nod] = 0;
         for(int i = 0; i < graf[nod].size(); ++i){
             int vecin = graf[nod][i].first;
             int cost = graf[nod][i].second;
             if(noduri[nod] + cost < noduri[vecin]){
                 noduri[vecin] = noduri[nod] + cost;
                 if(fol[vecin] == 0) coada.push(vecin), fol[vecin] = 1;
             }
         }
     }
 }
 int main(){
     in>>n>>m;
     for(int i = 1; i <= m; ++i){
         int x, y, c;
         in>>x>>y>>c;
         graf[x].push_back(make_pair(y,c));
     }
     dijkstra(1);
     for(int i = 2; i <= n; i++)
         if(noduri[i] != INF) out<<noduri[i]<<" ";
         else out<<0<<" ";
     return 0;
 }