#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define add push_back
#define inf 0x3f3f3f3f

using namespace std;
int n, m;
int d[50005];
vector<pair<int,int> > v[50005];
priority_queue<pair<int,int> >q;

void Citire()
{
   int i, a, b, c;
   scanf("%d %d", &n, &m);
   for (i=1; i<=m; i++)
   {
      scanf("%d %d %d", &a, &b, &c);
      v[a].add(make_pair(c, b));
   }
}

void Init()
{
   int i;
   q.push(make_pair(0, 1));
   memset(d, inf, sizeof(d));
   d[1]=0;
}

void Solve()
{
   Init();
   pair<int,int> x;
   while(!q.empty())
   {
      x=q.top();
      q.pop();
      for (vector<pair<int,int> >::iterator it=v[x.second].begin(); it!=v[x.second].end(); ++it)
         if (d[it->second]>d[x.second]+it->first)
         {
            d[it->second]=d[x.second]+it->first;
            q.push(*it);
         }
   }
}

void Afis()
{
   int i;
   for (i=2; i<=n; i++)
      printf("%d ", d[i]);
}

int main()
{
   freopen("dijkstra.in", "r", stdin);
   freopen("dijkstra.out", "w", stdout);
   Citire();
   Solve();
   Afis();

   return 0;
}