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

using namespace std;

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

int n, m;

const int NMax = 50002;
const int oo = (1 << 31) - 1;

int D[NMax], viz[NMax];

struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};

vector < pair < int, int > > G[NMax];

priority_queue< int, vector <int>, compara > coada, aux;

void citeste()
{
    fin >> n >> m;

    for(int i = 1 ; i <= m ; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y,c));

    }
}


void afisare()
{
    for(int i = 2 ; i <= n ; i++)
    {
        if( D[i] != oo)
        fout << D[i] << " ";
        else
            fout << 0 << " ";
    }
}

void Dijkstra(int start)
{
    for(int i = 1 ; i <= n ; i++)
        D[i] = oo;
    D[start] = 0;
    coada.push(start);
    viz[start] = true;

    while(!coada.empty())
    {
        int curent = coada.top();
      //  afisareCoada();
        coada.pop();
        viz[curent] = false;


        for(auto i : G[curent])
        {
            int vecin = i.first;
            int cost = i.second;
            if( D[curent] + cost < D[vecin])
            {
                D[vecin] = D[curent] + cost;
                if( viz[vecin] == false)
                {
                    coada.push(vecin);
                    viz[vecin] = true;
                }
            }
        }

    }
}
int main()
{
    //cout << oo;
    citeste();
    Dijkstra(1);
    afisare();

}