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

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

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

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(make_pair(b,c));
    }
    for(int i=2; i<=n; ++i) dist[i]=MULT;
    int cmin,bnod;
    for(int i=1; i<=n; ++i) {
      cmin=MULT,bnod=-1;
      for(int j=1; j<=n; ++j) if(!fol[j] && dist[j]<cmin) {
        cmin=dist[j];
        bnod=j;
      }
      for(it j=gr[bnod].begin(); j!=gr[bnod].end(); ++j) dist[j->x]=min(dist[j->x],dist[bnod]+j->y);
      fol[bnod]=1;
    }
    for(int i=2; i<=n; ++i)
      if(dist[i]==MULT) g<<"0 ";
      else g<<dist[i]<<' ';
    return 0;
}