#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define DN 50005
#define x first
#define y second
#define MULT (1<<30)
#define mp make_pair
using namespace std;

typedef pair<int,int> per;
typedef vector<per>::iterator it;

int n,m,dist[DN],fol[DN];
vector<per> gr[DN];
set<per> s;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(;m;--m) {
      int a,b,c;
      f>>a>>b>>c;
      gr[a].push_back(mp(b,c));
    }
    for(int i=2; i<=n; ++i) dist[i]=MULT;
    s.insert(mp(0,1));
    for(;s.size();) {
      for(;s.size() && (dist[s.begin()->y]<s.begin()->x || fol[s.begin()->y]);s.erase(s.begin()));
      if(s.empty()) continue;
      int bnod=s.begin()->y;
      fol[bnod]=1;
      //cout<<bnod<<' ';
      for(it i=gr[bnod].begin(); i!=gr[bnod].end(); ++i) {
        dist[i->x]=min(dist[i->x],dist[bnod]+i->y);
        s.insert(mp(dist[i->x],i->x));
      }
    }
    for(int i=2; i<=n; ++i)
      if(dist[i]==MULT) g<<"0 ";
      else g<<dist[i]<<' ';
    return 0;
}