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


using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct legatura{
    int destinatie, cost;
};

struct nod{
    int nr, lungime, vizitat;
    vector <legatura> legaturi;
};

vector<nod> noduri;
vector<int> coada;
int n;


int main()
{
    int m, i, a, b, c;

    int s = 1;

    f>>n>>m;
    for (i = 0; i  < n; i++)
    {
        nod nou;
        nou.nr = i + 1;
        nou.lungime = 0;
        nou.vizitat = 0;

        if (i == s - 1)
        {
            nou.lungime = 0;
            nou.vizitat = 1;
        }



        noduri.push_back(nou);
    }

    for (i = 0; i < m; i++)
    {
        f>>a>>b>>c;
        //noduri[b-1].ordin++;
        legatura nou;
        nou.destinatie = b - 1;
        nou.cost = c;
        noduri[a-1].legaturi.push_back(nou);
    }

    coada.push_back(s - 1);

    while (!coada.empty())
    {
        int minCoada = 0;
        for (i = 1; i < coada.size(); i++)
            if (noduri[coada[i]].lungime < noduri[coada[minCoada]].lungime && noduri[coada[i]].vizitat == 1)
                minCoada = i;

        int nodCurent = coada[minCoada];
        coada.erase(coada.begin() + minCoada);

        int lg = noduri[nodCurent].lungime;
        for (i = 0; i < noduri[nodCurent].legaturi.size(); i++)
        {
            int nodNou = noduri[nodCurent].legaturi[i].destinatie;
            int costTotal = lg + noduri[nodCurent].legaturi[i].cost;

            if (costTotal < noduri[nodNou].lungime || noduri[nodNou].vizitat == 0)
            {
                noduri[nodNou].vizitat = 1;
                noduri[nodNou].lungime = costTotal;
                coada.push_back(nodNou);
            }
        }
    }

    for (i = 1; i < n; i++)
        g<<noduri[i].lungime<<" ";

    return 0;
}