#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

class nod_graf
{
public:
    int val_muchie;
    int nr_nod;
    bool operator<(const nod_graf &other) const
    {
        return val_muchie > other.val_muchie;
    }
};

class val_heap
{
public:
    int val;
    int nr_nod;
    bool operator<(const val_heap &other) const
    {
        return val > other.val;
    }
};

vector<nod_graf> G[50002];
vector<int> val_drum_optim(50002);
priority_queue<val_heap> min_heap_valori_drumuri;

int n, m;

void dijkstra()
{
    while (!min_heap_valori_drumuri.empty())
    {
        val_heap nod_curent = min_heap_valori_drumuri.top();
        min_heap_valori_drumuri.pop();
        for (int i = 0; i < G[nod_curent.nr_nod].size(); i++)
        {
            nod_graf nod_graf_curent;
            val_heap valoare_de_ad_heap;
            nod_graf_curent = G[nod_curent.nr_nod][i];
            valoare_de_ad_heap.nr_nod = nod_graf_curent.nr_nod;
            valoare_de_ad_heap.val = val_drum_optim[nod_curent.nr_nod] + nod_graf_curent.val_muchie;
            if (valoare_de_ad_heap.val < val_drum_optim[valoare_de_ad_heap.nr_nod])
            {
                val_drum_optim[valoare_de_ad_heap.nr_nod] = valoare_de_ad_heap.val;
                min_heap_valori_drumuri.push(valoare_de_ad_heap);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    nod_graf nodul;
    val_drum_optim.assign(n + 1, INT16_MAX);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        nodul.nr_nod = b;
        nodul.val_muchie = c;
        G[a].push_back(nodul);
    }
    val_heap nodul_de_start;
    nodul_de_start.nr_nod = 1;
    nodul_de_start.val = 0;
    val_drum_optim[1] = nodul_de_start.val;
    min_heap_valori_drumuri.push(nodul_de_start);
    dijkstra();
    for (int i = 2; i <= n; i++)
    {
        if (val_drum_optim[i] != INT32_MAX) 
            fout << val_drum_optim[i] << " ";
        else
            fout << "0 ";
    }
    fout << "\n";
    return 0;
}