#include <iostream>
#include<fstream>
#include<vector>
#define noduri 50001
#define muchii 250001
#define val_max 1000000
using namespace std;
void min_heapify(int *a, int i, int n, int d[],int poz[]) // pune el. a[i] la locul lui  O(logi)
{
    int j;
    int aux;
    aux = a[i];
    int d_aux = d[a[i]];
    j = 2*i;//fiul stang =>introduc in vectorul initial de la 1, nu de la 0!
    while (j <= n)
    {
        if (j < n && d[a[j+1]] < d[a[j]])
        {
            j = j+1; //merg la fiul drept
        }
        if (d_aux < d[a[j]])
            break;//i-am gasit locul
        else if (d_aux >= d[a[j]])
        {
            poz[a[j]]=j/2;
            a[j/2] = a[j];
            j = 2*j;//continui pe arborele stang sa aranjez
        }
    }
    poz[aux]=j/2;
    a[j/2] = aux; // pun el care era pe poz i, la locul lui
}

void build_minheap(int *a, int n, int d[],int poz[])
{
    int i;
    for(i = n/2; i >= 1; i--) //pornesc de la jumatate ca sa aiba sens "fiul stang 2*i" si fiul drept "2*i+1"
    {
        min_heapify(a, i, n, d, poz);
    }
}

int Decapitare (int *a, int &n, int d[],int poz[])
{
    swap(a[1],a[n]);
    n--;
    min_heapify(a,1,n,d,poz);
    return a[n+1];
}

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    int n;
    f>>n;
    int m;
    f>>m;
    int poz[noduri];
    for(int i=0;i<noduri;i++)
        poz[i]=0;
    int **cost_muchie;
    cost_muchie=new int* [noduri];
    for(int i=0; i<=m; i++)
    {
        cost_muchie[i]=new int[muchii];
    }
    vector<int>* la;
    la= new vector<int> [n+1];
    int x,y;
    for(int i =1; i<=m; i++)
    {
        f>>x>>y;
        f>>cost_muchie[x][y];
       // cost_muchie[y][x]=cost_muchie[x][y];
        la[x].push_back(y);
        //la[y].push_back(x);
    }
    int s=1;
    int Q[noduri];//multimea vf neselectate
    for(int i=1;i<=n;i++)
        {
            Q[i]=i;
            poz[i]=i;
        }
    int d[noduri];
    for(int i=0;i<=n;i++)//iau de la i=0 ca sa nu am probleme cu el de pe poz. 0 la construirea si repararea heap-ului
        d[i]=val_max;
  //  int tata[noduri];
  //  for(int i=0;i<=n;i++)
    //    tata[i]=0;

    d[s] = 0;
    build_minheap(Q,n,d,poz);
    int nr_Q = n;
    int u,v;
    while(nr_Q!=0)
    {
        u=Decapitare(Q,nr_Q,d,poz);
        for(int i=0;i<(int)la[u].size();i++)
        {
            v = la[u][i];
            if(d[u]+cost_muchie[u][v]<d[v])
            {
                d[v]=d[u]+cost_muchie[u][v];
                min_heapify(Q,poz[v],nr_Q,d,poz);
              //  tata[v]=u;
            }
        }
    }

    for(int i=2;i<=n;i++)
    {
        g<<d[i]<<" ";
    }
    f.close();
    return 0;
}