#include <fstream>
#include <queue>
using namespace std;
ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");
struct nod
{
  int nr;
  long long dist;
} noduri[50005],el;
int nr_arc,nr_nod,i,ni,nf,c,el2,d,lg[50005];
bool valid[50005];
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);
      lg[ni]++;
    }
    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();
      valid[el.nr]=true;
      for (i=0;i<lg[el.nr];i++)
      {
          el2=snod[el.nr][i];
          if (valid[el2]==false)
          {
            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++) if (noduri[i].dist!=1000000000) fo<<noduri[i].dist<<' ';
    else fo<<0<<' ';
    return 0;
}

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