#include <fstream>
#include <vector>

using namespace std;

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

struct arc
{
    int nod, cost;
};
vector<arc>v[50001];

struct heap
{
    int val, poz;
}h[50001];
const int INF=1e9;
int n,d[50001],viz[50001],pre[50001],cn,indinheap[50001];

void up(int i)
{
    while(i>1&&(h[i].val<h[i/2].val))
    {
        swap(h[i],h[i/2]);
        indinheap[h[i].poz]=i/2;
        indinheap[h[i/2].poz]=i;
        i/=2;
    }
}
void down(int i){
  while(2*i+1<=n && (h[i].val>h[2*i].val||h[i].val>h[2*i+1].val))
      {
        if(h[2*i].val<h[2*i+1].val)
       {
          swap(h[i],h[2*i]);
          indinheap[h[i].poz]=2*i;
          indinheap[h[2*i].poz]=i;
          i=2*i;
       }
       else
       {
         swap(h[i], h[2*i+1]);
         indinheap[h[i].poz]=2*i+1;
         indinheap[h[2*i+1].poz]=i;
         i=2*i+1;
       }

      }

   if(i*2 == n && h[i].val> h[2*i].val){
     swap(h[i],h[2*i]);
     indinheap[h[i].poz]=2*i;
     indinheap[h[2*i].poz]=i;
   }

}
int main()
{
    int m;
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int x;
        fin>>x;
        arc aux;
        fin>>aux.nod>>aux.cost;
        v[x].push_back(aux);
    }
    d[1]=0;
    viz[1]=1;
    for(int i=2; i<=n; i++)
    {
        d[i]=INF;
    }
    for(int i=1; i<=n; i++)
    {
        h[i].poz=i;
        h[i].val=d[i];
        indinheap[i]=i;
    }
    int cn=n;
    int pas=1, gata=0, Min, indmin;
    for(pas=1; pas<n&&!gata; pas++)
    {
        /// selectez minimul din heap, dintre cei nevizitati, trebuie sa ii stiu si indicele
        Min=h[1].val;
        indmin=h[1].poz;
        h[1]=h[cn];
        cn--;
        if(cn>0) down(1);
        if(Min==INF)
            gata=1;
        else
        {
            viz[indmin]=1;
            int lg=v[indmin].size();
            for(int i=0; i<lg; i++)
            {
                int valoare=d[indmin]+v[indmin][i].cost;
                if(valoare<d[v[indmin][i].nod])
                {
                    d[v[indmin][i].nod]=valoare;
                    h[indinheap[v[indmin][i].nod]].val=valoare;
                    up(indinheap[v[indmin][i].nod]);
                }

            }
        }

    }
    for(int i=2; i<=n; i++)
    {
        if(d[i]!=INF)
            fout<<d[i]<<" ";
        else fout<<0<<" ";
    }
    return 0;
}