#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define oo (1<<30)
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m, d[250001], viz[250001];
vector <pair <int , int > >v[250001];
struct compara
{ int operator() (int x, int y)
   {
      return d[x]>d[y];
   };
};
priority_queue < int ,vector <int>, compara > coada;
void citire()
{fin >> n >> m;
int x,y, z;
 for (int i=1;i<=m;i++)
     {fin >> x >> y >> z;
      v[x].push_back(make_pair(y, z));
     }
}
void Dijkstra (int k)
{for (int i=1;i<=n;i++)
      d[i]=oo;
d[k]=0;
coada.push(k);
viz[k]=1;
while (!coada.empty())
      {int cur=coada.top();
       coada.pop();
       viz[cur]=1;
       for(unsigned int i=0;i<v[cur].size();i++)
          {int a=v[cur][i].first;
           int b=v[cur][i].second;
           if(d[cur]+b<d[a])
             {d[a]=d[cur]+b;
              if(viz[a]==0)
                {viz[a]=1;
                coada.push(a);
                }
             }
          }
      }
}
void afisare ()
{for (int i=2;i<=n;i++)
     {if(d[i]==oo)
          fout << -1 << " ";
     else fout << d[i] << " ";
     }
}
int main()
{citire();
Dijkstra (1);
afisare();
    return 0;
}