#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#define infinit 2000000000

using namespace std;


int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n,m,k;

    fin>>n>>m;


// Dijkstra


    int a,b,costul,i;
    int d[n+1],tata[n+1];
    set <pair <int, int> > nS;
    vector <pair<int, int> > la[n+1];

    for(i=1;i<=n;i++)
        {
            d[i]=infinit;
            tata[i]=0;
        }

    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>costul;
        la[a].push_back(make_pair(costul,b));
    }

/*
cout<<"Listele:"<<"\n";
    for(i=1;i<=n;i++)
    {cout<<"lista lui "<<i<<":  ";
     for(int j=0;j<la[i].size();j++)
            cout<<la[i][j].second<<" "<<la[i][j].first<<", ";
    cout<<"\n";
    }
    */

    nS.insert(make_pair(0, 1));

    d[1]=0;



    while(!nS.empty())
    {
        int nod_min=nS.begin()->second;
        int dist_min=nS.begin()->first;

        nS.erase(nS.begin());

        int dim=la[nod_min].size();

        for(i=0;i<dim;i++)
        {

            int nod_adiacent=la[nod_min][i].second;
            int cost_muchie=la[nod_min][i].first;
            if(d[nod_adiacent]>dist_min+cost_muchie)
                {
                    if(d[nod_adiacent]!=infinit)
                        nS.erase(make_pair(d[nod_adiacent],nod_adiacent));
                   d[nod_adiacent]=dist_min+cost_muchie;
                   nS.insert(make_pair(d[nod_adiacent],nod_adiacent));
                }
        }

    }


    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";


    return 0;
}