#include <iostream>
#include<vector>
#include<fstream>
#include<queue>
#define Nmax 1000001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,n1,i,j,x,y,cst,dist[50001];
bool explored[50001];
vector< pair<int,int> >v[50001];
struct node_cost
{
  int node;
  int cost;

  bool operator<(const node_cost &o) const
  {
    return cost > o.cost; //normally this is still '<', but here I wanted to change the effect on the heap (make it MIN heap)
  }
};
priority_queue<node_cost>pq;

int main()
{
    f>>n>>m;
    n1=n;
    for(i=1;i<=m;i++)
    {
      f>>x>>y>>cst;
      v[x].push_back(make_pair(y,cst));
    }
    node_cost o;
    o.cost = Nmax;
    for(i=2;i<=n;i++) //for every node
    {
      o.node = i;
      pq.push(o);//insert every node in heap with cost = infinity
      dist[i] = Nmax; //distance from node 1 to node i
    }
    o.node = 1;
    o.cost = 0;
    pq.push(o);
    dist[1] = 0; //distance from node 1 to itself

    while(!pq.empty()) //while the heap is non empty
    {
      int i=pq.top().node;
      if(!explored[i])
      for(int k=0;k<v[i].size();k++) //for each neighbor
        if(!explored[v[i][k].first])
        {
          j=v[i][k].first; //neighbor is j
          if(dist[j] > dist[i] + v[i][k].second)
          {
            dist[j] = dist[i] + v[i][k].second; //update distance to j
            node_cost o;
            o.node = j;
            o.cost = dist[j];
            pq.push(o); //update heap
          }
        }
      pq.pop();
      explored[i] = true;
    }
    for(i=2;i<=n;i++)
      if(dist[i]!=Nmax)
        g<<dist[i]<<' ';
      else
        g<<0<<' ';
}