#include <fstream>
#include <queue>
using namespace std;
ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");
struct nod
{
  int nr;
  long long dist;
} noduri[20005],el;
int nr_arc,nr_nod,i,ni,nf,c,el2,d,lg;
struct cmp {
  bool operator()(const nod& a, const nod& b) const {
    return (a.dist > b.dist); // descrescator
  }
};
priority_queue<nod, vector<nod>, cmp> pq;
vector <int> snod[50005],cost[50005];
int main()
{
    fi>>nr_nod>>nr_arc;
    for (i=1;i<=nr_arc;i++)
    {
      fi>>ni>>nf>>c;
      snod[ni].push_back(nf);
      cost[ni].push_back(c);
    }
    for (i=1;i<=nr_nod;i++) noduri[i].dist=1000000000;
    for (i=1;i<=nr_nod;i++) noduri[i].nr=i;
    noduri[1].dist=0;
    pq.push(noduri[1]);
    while (!pq.empty())
    {
      el=pq.top();
      pq.pop();
      lg=snod[el.nr].size();
      for (i=0;i<lg;i++)
      {
        el2=snod[el.nr][i];
        d=el.dist+cost[el.nr][i];
        if (d<noduri[el2].dist)
        {
          noduri[el2].dist=d;
          pq.push(noduri[el2]);
        }
      }
    }
    for (i=2;i<=nr_nod;i++) fo<<noduri[i].dist<<' ';
    return 0;
}

// v[x].q1.push_back(y);
// cost[x].push_back(c);
// vector<unsigned short int> v[LIMITA], cost[LIMITA];