#include <bits/stdc++.h>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#define pb push_back
#define pp pop_back
#define mp make_pair

int const lim=50001;
int const oo = ( 1 << 30);

int n,m,d[lim],vl[lim];
bool ver[lim];



vector < pair < int , int > > c[lim];

struct comp
{
    bool operator()(int a, int b)
    {
        return d[a]<d[b];
    }
};

priority_queue < int, vector < int> , comp > cod;

void cit()
{int x,y,z;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {in>>x>>y>>z;
        c[x].pb(mp(y,z));
    }
}

void dij(int nod)
{
    for(int i=1;i<=n;i++)
        d[i]= oo;

    d[nod]=0;
    cod.push(nod);
    ver[nod]= true;

    while(!cod.empty())
    {
        int nx=cod.top();
        cod.pop();
        ver[nx] = false;

        for(int i=0; i<c[nx].size(); i++)
        {
          int  vecin= c[nx][i].first;
          int  cost= c[nx][i].second;
          if(d[nx] + cost < d[vecin])
          {
              d[vecin]=d[nx] + cost;
              if(ver[vecin]==0)
              {
                  cod.push(vecin);
                  ver[vecin]=1;
              }
          }

        }

    }
}

int main()
{
    cit();
    dij(1);

    for(int i=2;i<=n;i++)
      if(d[i]!=oo)  out<<d[i]<<" ";
      else out<<0<<" ";
}