#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <list>
#include <algorithm>
 
#define Nmax 500005
#define inf 1000000
 
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
int N, M;
int D[Nmax]; // D[i] – distanta minima intre nodul de start si nodul numarul i
bool VerifCoada[Nmax];
 
vector<pair <int,int> >graf_ponderat[Nmax];
priority_queue<pair <int,int> >q;
 
class Graf{
private:
    int Nr_Noduri, Nr_Muchii;
    vector<int> GRAF[Nmax]; // lista de adiacenta
    // pair< int, pair<int,int> > graf_ponderat[400010];   // lista de adiacenta pentru graf ponderat
 
public:
    Graf(int N, int M); // constructor
    void Citire_Dijkstra();
    void Dijkstra( int nod );
    void Afisare_Dijkstra();
};
 
// constructor
Graf :: Graf(int N, int M)
{
    Nr_Noduri = N;
    Nr_Muchii = M;
}
 
void Graf :: Citire_Dijkstra()
{
    for ( int i = 1; i <= Nr_Muchii; i++ )
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        graf_ponderat[x].push_back(make_pair(cost, y));
    }
}
 
void Graf :: Dijkstra(int nodStart)
{   
    // setam vectorul pe inf
    for ( int i = 1; i <= Nr_Noduri; i++ )
        D[i] = inf;
 
    // distanta pana la nodul de start = 0
    D[nodStart] = 0;
 
    // Punem nodul de start in coada
    q.push(nodStart);
    VerifCoada[nodStart] = 1;
 
    while ( !q.empty() )
    {
        // extragem nodul curent
        int nod = q.top();
 
        VerifCoada[nod] = 0;
        for ( int i = 0; i < graf_ponderat[nod].size(); i++ )
        {
            int vecin = graf_ponderat[nod][i].first;
            int cost = graf_ponderat[nod][i].second;
            // daca gasim o distanta mai mica
            if ( D[nod] + cost < D[vecin] )
            {
                D[vecin] = D[nod] + cost;
                // daca vecinul nu se afla in coada il adaugam
                if ( VerifCoada[vecin] == 0 )
                {
                    q.push(vecin);
                    VerifCoada[vecin] = 1;
                }
            }
        }
        q.pop();
    }
}
 
void Graf :: Afisare_Dijkstra()
{
    for ( int i = 2; i <= Nr_Noduri; i++ )
    {
        if ( D[i] != inf )
            fout << D[i] << " ";
        else 
            fout << "0 ";
    }
}
 
int main()
{
    fin >> N >> M;
    Graf G(N, M);
    G.Citire_Dijkstra();
    G.Dijkstra(1);
    G.Afisare_Dijkstra();
    
    return 0;
}