#include <fstream>
#include <queue>
#define nmax 50005

using namespace std;

int n, m;
vector<pair<int,int> > gf[nmax];
int d[nmax];

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void citeste(){

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

}

struct cmp{

   bool operator() (pair<int,int> a, pair<int,int> b){
      return a.first > b.first;
   }

};

void dijkstra(){

   for(int i=0; i<nmax; i++) d[i] = (1<<30);

   d[1] = 0;

   priority_queue<pair<int,int>, vector<pair<int,int> >, cmp > heap;
   heap.push(make_pair(0, 1));

   for(; heap.size(); ){
      int nod = (heap.top()).second;
      int Min = (heap.top()).first;
      heap.pop();
      for(int i=0; i<gf[nod].size(); i++){
         int vc = gf[nod][i].first;
         int cost = gf[nod][i].second;
         if (d[vc] > Min + cost){
            d[vc] = Min + cost;
            heap.push(make_pair(d[vc], vc));
         }
      }
   }

}

void scrie(){

   for(int i=2; i<=n; i++)
      if (d[i] == (1<<30) ) g << 0 << " ";
      else g << d[i] << " ";

}

int main(){

   citeste();
   dijkstra();
   scrie();

   f.close();
   g.close();

   return 0;

}