#include<fstream>
#include<vector>
#include<queue>
#define inf  0x3f3f3f
#define dim 50005
#include<iostream>

using namespace std;

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

struct rtt
{
    int n,c;

};

vector <vector<rtt> > a(dim);
vector <int> d(dim,inf);
vector <bool> inq(dim,false);
queue <int> q;

int nn,m;

void citire()
{
  int x0,y0,cc;

    in>>nn;
    in>>m;
    for (int i=1;i<=m;++i)
     {
         in>>x0>>y0>>cc;
         a[x0].push_back((rtt){y0,cc});
     }
}

void bell(int nod)
{
    int i;
    q.push(nod);
    d[nod]=0;
inq[nod]=true;

    while (!q.empty())
    {
        nod=q.front();
        q.pop();
        inq[nod]=false;
        for ( i=0;i<a[nod].size();++i)
          if (d[a[nod][i].n]>d[nod]+a[nod][i].c)
            {d[a[nod][i].n]=d[nod]+a[nod][i].c ;
          if (inq[a[nod][i].n]==false)
             {q.push(a[nod][i].n);inq[a[nod][i].n]=true;}
            }


    }


}


int main()
{
    citire();

    bell(1);

    for (int i=2;i<=nn;++i)
      if (d[i]!=inf) out<<d[i]<<" ";
       else out<<"0";


    return 0;
}