#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000000;

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,x,c,d[50001],g[50001];

struct nod {int nod,val;}p;
queue<int>C;
vector <nod> v[50001];

int main()
{ int i;
  fin>>n>>m;
  for(i=1; i<=m; ++i)
      { fin>>x>>p.nod>>p.val;
        v[x].push_back(p);
        g[x]++;
      }
  C.push(1);
 for(i=1; i<=n; i++)
     d[i]=1000000000;
 d[1]=0;
 while(C.size()>0)
     { c=C.front();
       C.pop();
       for(i=0; i<g[c]; i++)
           if(v[c][i].val+d[c]<d[v[c][i].nod])
            { d[v[c][i].nod]=v[c][i].val+d[c];
              C.push(v[c][i].nod);
            }
     }
  for(i=2; i<=n; ++i)
      if(d[i]==1000000000) fout<<"0";
      else fout<<d[i]<<" ";
  return 0;
 }