#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define Nmax 50005

using namespace std;

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

vector < pair < int, int > > Numbers[Nmax];

priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > Coada;

int Distanta[Nmax];

int vf, muchii, a, b, cost;

void Dijkstra(int x)
{
    int Vecin, Cost, Nod;

    Coada.push({x, 0});

    while(!Coada.empty())
    {
        Nod = Coada.top().first;
        Cost = Coada.top().second;

        Coada.pop();

        if(Cost > Distanta[Nod])
            continue;

        for(unsigned int i = 0; i < Numbers[Nod].size(); ++ i)
        {
            Vecin = Numbers[Nod][i].first;
            Cost = Numbers[Nod][i].second;

            if(Distanta[Nod] + Cost < Distanta[Vecin])
            {
                Distanta[Vecin] = Distanta[Nod] + Cost;
                Coada.push({Vecin, Distanta[Vecin]});
            }
        }

    }
}

int main()
{
    fin >> vf >> muchii;
    for(int i = 1; i <= muchii; ++ i)
    {
        fin >> a >> b >> cost;
        Numbers[a].push_back({b, cost});
    }
    Distanta[1] = 0;
    for(int i = 2; i <= vf; ++ i)
        Distanta[i] = 1e9;
    Dijkstra(1);
    for(int i = 2; i <= vf; ++ i)
        fout << Distanta[i] << " ";
    return 0;
}