#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define siz 50100

using namespace std;

struct nod {
 long csp,ta;
} adat;


long n,m,i,u,x,y,t;
long dist[siz];
vector<nod> v[siz];

class comp{
public:
    bool operator()(long& a, long& b) {
      if(dist[a]<dist[b]) return true;
	  return false;
    }
};

priority_queue<long, vector<long>, comp> heap;

int main()
{
 ifstream in("dijkstra.in");
 ofstream out("dijkstra.out");

 in >> n >> m;
 for(i=1;i<=m;++i){
   in >> x >> y >> t;
   adat.csp=y;
   adat.ta=t;
   v[x].push_back(adat);
 }

 for(i=1;i<=n;++i) dist[i]=INF;
 dist[1]=0;
 heap.push(1);

 while(!heap.empty()) {
  u=heap.top();
  heap.pop();
  for (i=0;i<(long)v[u].size();++i) {
   if (dist[v[u][i].csp]>dist[u]+v[u][i].ta) {
      dist[v[u][i].csp]=dist[u]+v[u][i].ta;
      heap.push(v[u][i].csp);
   }
  }
 }

 for(i=2;i<=n;++i){
    if(dist[i]==INF) out << "0 ";
    else out << dist[i] << " ";
 }

 in.close();
 out.close();

 return 0;
}