#include <fstream>
#include <queue>
#include <vector>
#define f first
#define s second

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
vector<pair<int,int> > v[50001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;
int d[50001],n,m,a,b,c,nod,i;
bool viz[50001];
int main()
{
   in>>n>>m;
   for(i=1;i<=m;i++)
   {
       in>>a>>b>>c;
       v[a].push_back(make_pair(c,b));
   }
   for(i=1;i<=n;i++)
   {
       d[i]=1000000001;
   }
   d[1]=0;
   h.push(make_pair(0,1));
   while(!h.empty())
   {
       nod=h.top().second;
       h.pop();
       if(!viz[nod])
       {
           for(i=0;i<v[nod].size();i++)
           {
               if(d[v[nod][i].s]>d[nod]+v[nod][i].f)
               {
                   d[v[nod][i].s]=d[nod]+v[nod][i].f;
                   h.push(make_pair(d[v[nod][i].s],v[nod][i].s));
               }
           }
           viz[nod]=1;
       }

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