#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <int> v[50005],d[50005];

int n,m,dmin[50005],use[50005];

struct elem
{int x,dist; } el;

struct comp
{

bool operator() (elem a,elem b)
{ return a.dist>b.dist;}

};

priority_queue<elem,vector<elem>,comp> heap;

void Dijk()
{ int i,nod,nod2;
    el.x=1; el.dist=0;
    heap.push(el);

    for(i=2;i<=n;i++)
     dmin[i]=inf;

   while(!heap.empty())
   { el=heap.top(); heap.pop();
     nod=el.x; if (use[nod]) continue;
     use[nod]=1;

      for(i=0;i<v[nod].size();i++)
       if (!use[v[nod][i]])
       { nod2=v[nod][i];

         if (dmin[nod]+d[nod][i]<dmin[nod2])
         { el.x=nod2; el.dist=dmin[nod]+d[nod][i];
           dmin[el.x]=el.dist;
           heap.push(el);
         }

       }
   }
}

int main()
{ int i,x,y,dst;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>dst;
       v[x].push_back(y);
       d[x].push_back(dst);
    }

    Dijk();
    for(i=2;i<=n;i++)
     if (!use[i]) g<<"0\n";
        else g<<dmin[i]<<" ";
    return 0;
}