#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#include<list>
#include<stack>
#include <set>
#include <cstring>
# define INF 0x3f3f3f3f
const int NMAX = 50005;
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

class Graf{

    private:
        int noduri, muchii;
        list <int> *adiacenta;
        list <int> *adiacenta_trans;
        vector<int> cost_vizita;
        stack <int> stiva_topo;
        void DFS(int sursa);
        void SortareTopologica(int sursa);
        void DFSCTC(int nod);
        void GTranspus(int fiu, int tata);
        void Ordine(int nod, stack<int>& stiva);
public:
    Graf(); //constructor neparametrizat
    Graf(int nr_noduri, int nr_muchii); //constructor parametrizat - in functie de nr de noduri si muchii
    ~Graf(); //destructorul

    void Muchie(int tata, int fiu); //adaug o muchie in graful curent orientat
    void BFS(int sursa);
    void ComponenteConexe();
    void Sortare();
    void CTC();
};
class GrafCosturi {
    int noduri;
    int distante[NMAX];
    vector<pair<int, int>> adiacenta[NMAX];
public:
    GrafCosturi(int V);
    void MuchieCost(int u, int v, int w);
    void Djisktra(int sursa);
};
GrafCosturi::GrafCosturi(int V)
{
    this->noduri = noduri;
}
void GrafCosturi::MuchieCost(int sursa, int destinatie, int cost)
{
    adiacenta[sursa].push_back(make_pair(destinatie, cost));
}
void GrafCosturi::Djisktra(int sursa)
{
    set< pair<int, int> > cost_minim;
    memset(distante, INF, sizeof distante);
    cost_minim.insert(make_pair(0, sursa));
    distante[sursa] = 0;
    while (!cost_minim.empty())
    {
        int node = cost_minim.begin()->second;
        int d = cost_minim.begin()->first;
        cost_minim.erase(cost_minim.begin());

        for (vector<pair<int, int>>::iterator it = adiacenta[node].begin(); it != adiacenta[node].end(); ++it) {
            int to = it->first;
            int cost = it->second;
            if (distante[to] > distante[node] + cost) {
                if (distante[to] != INF) {
                    cost_minim.erase(cost_minim.find(make_pair(distante[to], to)));
                }
                distante[to] = distante[node] + cost;
                cost_minim.insert(make_pair(distante[to], to));
            }
        }
    }

    for (int i = 2; i <= noduri; ++i) {
        if (distante[i] == INF) {
            distante[i] = 0;
        }
        g << distante[i] << ' ';
    }
}

Graf::Graf() //constructor neparametrizat - valori implicite = 0
{
    this->noduri = 0;
    this->muchii = 0;
}
Graf::Graf(int nr_noduri, int nr_muchii) //constructor parametrizat - in functie de nr de noduri si muchii
{
    this->noduri = nr_noduri; //initializez dimensiunile grafului cu cele citite din fisier
    this->muchii = nr_muchii;
    adiacenta = new list<int>[nr_noduri];
    adiacenta_trans = new list<int>[nr_noduri];
    cost_vizita.resize(nr_noduri, -1); //definesc un vector unde contorizez pe parcursul BFS-ului ce noduri au fost vizitate si care e distanta catre nodul parinte, initializarea se face cu valoarea -1
}
Graf::~Graf() //destructorul
{ 
    this->noduri = 0;
    this->muchii = 0;
    delete [] adiacenta;
    cost_vizita.clear(); //eliberez spatiul alocat vectorului unde contorizez nodurile vizitate
}
void Graf::Muchie(int tata, int fiu) 
{
    adiacenta[tata - 1].push_back(fiu - 1); //adaug pe linia tata - 1, ca ultim element al vetorului, nodul cu care se invecineaza (fiu - 1) - le adaug -1 pentru ca eu lucrez cu vectori care incep de la 0
}
void Graf::BFS(int sursa)
{
    queue<int> vecini; //coada in care aduag pe rand nodurile pe care le voi parcurge in BFS
    cost_vizita[sursa - 1] = 0; //costul de vizita al nodului sursa e 0
    vecini.push(sursa - 1); //adaug nodul sursa in coada BFS
    while (!vecini.empty()) { //cat timp am noduri accesibile din radacina
        int nod_curent = vecini.front(); //iau nodul din fata cozii si adaug la finalul cozii toti vecinii cu care acesta are conexiuni
        vecini.pop();
        for (auto& nod_vecin : adiacenta[nod_curent]) //iau din lista de adiacenta nodurile vecine
        {
            if (cost_vizita[nod_vecin] == -1) { //verific ca nodul sa nu fi fost deja vizitat
                cost_vizita[nod_vecin] = cost_vizita[nod_curent] + 1; //daca nodul nu a fost vizitat, ii calculez costul de vizita
                vecini.push(nod_vecin);                               //si il adaug in coada pentru BFS
            }
        }
    }
    for (size_t i = 0; i < cost_vizita.size(); i++) //afisez costul pentru fiecare nod
        g << cost_vizita[i]<< " ";
}
void Graf::DFS(int sursa)
{
    cost_vizita[sursa] = 1; //marchez nodul sursa ca fiind vizitat
    for (auto& nod_vecin : adiacenta[sursa]) //verific in vecinii acestuia care nu au fost vizitati si apelez pentru fiecare in parte DFS
        if (cost_vizita[nod_vecin] == -1)
        {
            cost_vizita[nod_vecin] = 1; //actualizez starea nodului -> actualizat
            DFS(nod_vecin);
        }
 }
void Graf::ComponenteConexe()
{
    int nr_conexe = 0;
    for (size_t i = 0; i < cost_vizita.size(); i++) //din graful initial, verific nodurile care nu au fost vizitate si apelez DFS pentru fiecare in parte
        if (cost_vizita[i] == -1)
        {
            DFS(i); // fiecare apel independet de DFS imi semnaleaza existenta unei componente conexe
            nr_conexe++;
        }
    g << nr_conexe;
}
void Graf::SortareTopologica(int sursa)
{
    cost_vizita[sursa] = 1; // pornesc dintr-un varf sursa, iar dupa principiul DFS, voi realiza pentru fiecare nod gasit in adancime sortarea
    for (auto& nod_vecin : adiacenta[sursa])
        if (cost_vizita[nod_vecin] == -1)
            SortareTopologica(nod_vecin);
    stiva_topo.push(sursa); //cand nodul curent a ramas fara vecini accesibili, acesta este aduagat in stiva de sortare
}
void Graf::Sortare()
{
    for (size_t i = 0; i < cost_vizita.size(); i++) //din graful initial, verific nodurile care nu au fost vizitate si apelez Sortarea Topologica pentru fiecare in parte
        if (cost_vizita[i] == -1)
            SortareTopologica(i);
    while (!stiva_topo.empty())
    {
        g << stiva_topo.top()+1<<" "; //adaug 1 pt ca am scazut din fiecare numar 1
        stiva_topo.pop();
    }
}
void Graf::DFSCTC(int nod)
{
    cost_vizita[nod] = 1;
    cout << nod << " ";
    for (auto& nod_vecin : adiacenta_trans[nod]) //execut DFS pentru nodurile din graful transpus avand ca ordine de executie nodurile din stiva
        if (cost_vizita[nod_vecin] == -1)
           DFSCTC(nod);
}
void Graf::GTranspus(int fiu, int tata)
{
    adiacenta_trans[tata - 1].push_back(fiu - 1); //realizez graful transpus
}
void Graf::Ordine(int nod, stack<int>& stiva) 
{
    cost_vizita[nod] = 1;
    for (auto& nod_vecin : adiacenta[nod]) // execut un DFS si adaug nodurile in stiva dupa timpul lor de terminare (raman far vecini)
        if (cost_vizita[nod_vecin] == -1)
            Ordine(nod_vecin, stiva);
    stiva.push(nod);
}
void Graf::CTC()
{
    stack<int> stiva;
    for (size_t i = 0; i < cost_vizita.size(); i++) //din graful initial, verific nodurile care nu au fost vizitate si apelez DFS pentru fiecare in parte
        if (cost_vizita[i] == -1)
            Ordine(i, stiva);
    for (size_t i = 0; i < cost_vizita.size(); i++)
        cost_vizita[i] = -1;
    while (!stiva.empty())
    {
        int nod_curent = stiva.top();
        stiva.pop();
        if (cost_vizita[nod_curent] == -1) //pentru ordinea din stiva, execut DFS
        {
            DFSCTC(nod_curent);
            cout << endl;
        }
    }
}
/*bool HavelHakimi()
{
    ifstream f("hh.in");
    vector <int> grade;
    int n, grad, grade_impare = 0;
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> grad;
        if (grad > n)
            return false; //pas 1, verific sa nu existe un nod cu grad mai mare decat nr de elem
        if (grad % 2 == 1)
            grade_impare++; //calculez nr de grade impare ale nodurilor
        grade.push_back(grad);
    }
    if (grade_impare % 2 == 1)
        return false; //daca nr de grade impare ale nodurilor este un numar impar => nu se paote forma un graf cu acele grade
    while (1)
    {
        int k = 0, max = 0, no = 0;
        no = grade.size();
        for (auto& grad : grade)
            if (grad < 0) return false(); //daca exista grade negative, nu se paote forma un graf
            else if (grad == 0) k++; //calculez nr de elem cu grad 0
        if (k == no) return true; //daca toate elem sunt nule, atunci se poate forma graful
        sort(grade.begin(), grade.end(), greater<int>());
        max = grade[0]; //preiau elementul cel mai mare si il sterg din lista
        grade.erase(grade.begin());
        if (max > grade.size()) //daca cel mai mare grad e mai mare decat nr de elemnte din lista, at false
            return false;
        else
        {
            for (int i = 0; i < max; i++) //scad din primele max elemente cate 1 si reiau procesul
                grade[i]--;
        }

        f.close();
    }
} */
int main() {
    int N, M, S, x, y, z;
    f >> N >> M;
 /* Graf exbfs(N, M); //initializez graful
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        exbfs.Muchie(x, y);
    }
    exbfs.BFS(S); */
 /*   Graf exdfs(N, M); //initializez graful
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        exdfs.Muchie(x, y);
        exdfs.Muchie(y, x);
    }
    exdfs.ComponenteConexe(); */
 /*   Graf exsortt(N, M); //initializez graful
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        exsortt.Muchie(x, y);
    }
    exsortt.Sortare(); */
    /*Graf exctc(N, M); //initializez graful -- NU MERGE
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        exctc.Muchie(x, y);
        exctc.GTranspus(x, y);
    }
    exctc.CTC();*/
    /*if (HavelHakimi())
        cout << "DA!";
    else cout << "NU!";*/
    GrafCosturi exdjk(N);
    for (int i = 0; i < M; i++)
    {
        f >> x >> y >> z;
        exdjk.MuchieCost(x, y, z);
    }
    exdjk.Djisktra(1);
    return 0;
}