#include <queue>
#include <fstream>
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct Nod{
     int nod, cost;
 
     bool operator < (const Nod&e) const
     {
         return (cost > e.cost);
     }
};

vector <Nod> L[50009];
 
bool viz[50009];
int n,m,S;
int d[50009];
 
void Citire()
{
    int x,y,i, c;
    Nod w;
    fin >> n; // numarul de noduri
    fin >> m; // nr de muchii
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        w.nod = y; w.cost = c;
        L[x].push_back(w);
    }
}
 
void BFS(int k)
{      
    int i, j, c;
    priority_queue <Nod> q;
    Nod w;
    w.nod = k; w.cost = 0;
    q.push(w);
    viz[k] = 1;
    while (!q.empty())
    {
        k = q.top().nod;
        q.pop();
        for (j=0; j< L[k].size(); j++)
           {  i=L[k][j].nod; c=L[k][j].cost;
              if (!viz[i] || d[i] > d[k] + c)
              {  
                 d[i] = d[k] + c;
                 w.nod = i; w.cost=d[i];
                 q.push(w);
                 viz[i]=1;
              }
        }
    }
}
  
void Afisare()
{
    int i, j;
    for (i=2; i<=n; i++)
      fout << d[i] << " ";
    fout << "\n";
}
 
int main ()
{
    int i;
    Citire();
    BFS(1);
    Afisare();
    fin.close();
    fout.close();
    return 0;
}