#include <fstream>
#include <vector>
#include <queue>
#define INF 9999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,n,m,d[50001],viz[50001],nodac,costac,nod,cost,x,y;
struct cmp{
  bool operator()(pair<int,int> xx, pair<int, int> yy){
     return xx.second>yy.second;
  }

};
priority_queue< pair <int,int > ,vector <pair <int,int> >, cmp > heap;
vector <pair <int,int> > G[50001];
int main()
{
  f>>n>>m;
  for(i=2;i<=n;i++)
    d[i]=INF;
  heap.push(make_pair(1,0));
  for(i=1;i<=m;i++)
  {
      f>>x>>y>>cost;
      G[x].push_back(make_pair(y,cost));
  }
    while(!heap.empty()){
        nod=heap.top().first;
        heap.pop();
        if(viz[nod]==1)
            continue;
        viz[nod]=1;
        for(i=0;i<G[nod].size();i++)
        {
            nodac=G[nod][i].first;
            costac=G[nod][i].second;
            if(viz[nodac]==0)
                if(d[nodac]>d[nod]+costac)
            {
                d[nodac]=d[nod]+costac;
                heap.push(make_pair(nodac,d[nodac]));
            }
        }

    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)
        g<<d[i]<<" ";
        else
            g<<0<<" ";

    return 0;
}