#include <bits/stdc++.h>
#define nmax 50003
#define X get<0>
#define Y get<1>
#define COST get<2>
#define VIZ get<3>

using namespace std;

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


class graf {
/// tema 1
private:
    int n, m;
    vector<int> h[nmax];
    bitset<nmax> viz;

    int k, dist[nmax], nivel[nmax], mic[nmax];
    bool orientat = false;
    vector<int> transpus[nmax];
    vector<int> ctc[nmax];
    queue< pair<int, int> >q;
    stack<int> s;
    stack<int> s_biconex;
    vector<int> cbiconexe[nmax];
    vector< vector<int> > muchii;


    void dfs(int nod);

    void dfsctc(int nod);

    void bfs(int s);

    void dfs_biconex(int nod, int tata);

    void muchii_critice(int nod, int tata, vector< vector<int> >& h2);

public:
    graf()
    {
        n = m = k = 0;
    }

    void set_graf(int noduri, int muchii, bool Orientat);

    void adauga_muchie(int x, int y);

    void adauga_muchie(int x, int y, int cost);

    void componente_conexe();

    void distante(int s);

    void sortare_topologica();

    void componente_tare_conexe();

    void componente_biconexe();

    static void havel_hakimi();

    static vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections);


/// tema 2 ----------------------------------------------------------------------------------
private:
    vector < tuple < int, int, int, bool > > muchii_cost;
    vector<pair<int, int>> graf_cost[nmax];

    void Union(int x, int y, vector<int> &t);
    int Find(int x, vector<int> &t);
    int kruskal(int &n, int &m, vector<tuple<int, int, int, bool>> &muchii_cost, vector<int> &t);

    void dijkstra(int &start, vector<int> &d, vector<bool> &viz_coada);

public:
    void apm();
    void pb_dijkstra(int start);
};

graf g;


void graf :: set_graf(int noduri, int muchii, bool Orientat)
{
    n = noduri;
    m = muchii;
    orientat = Orientat;
}

void graf :: adauga_muchie(int x, int y)
{
    if(orientat)
    {
        h[x].push_back(y);
        transpus[y].push_back(x); // ctc
    }
    else
    {
        h[x].push_back(y);
        h[y].push_back(x);
    }
}

void graf :: adauga_muchie(int x, int y, int cost)
{
    if(orientat)
    {
        graf_cost[x].push_back({y, cost});
    }
    else
    {
        muchii_cost.push_back({x, y, cost, false});
    }
}

void graf :: dfs(int nod)
{
    viz[nod] = 1;
    for(auto i : h[nod])
        if(!viz[i])
            dfs(i);

    // pentru sortarea topologica si ctc
    s.push(nod);
}

void graf :: dfsctc(int nod)
{
    viz[nod] = 1;
    ctc[k].push_back(nod);
    for(auto i : transpus[nod])
        if(!viz[i])
            dfsctc(i);
}

void graf :: bfs(int s)
{
    pair<int, int> nod;
    q.push({s, 0});
    viz[s] = 1;
    dist[s] = 0;

    while(!q.empty())
    {
        nod = q.front();
        dist[nod.first] = nod.second;
        q.pop();

        for(auto i : h[nod.first])
            if(!viz[i])
            {
                q.push({i, nod.second + 1});
                viz[i] = 1;
            }
    }
}

void graf :: componente_conexe()
{
    int nrc;
    nrc = 0;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            dfs(i);
            nrc++;
        }
    fout << nrc << "\n";
}

void graf :: distante(int s)
{
    for(int i = 1; i <= nmax - 3; i++)
        dist[i] = -1;
    bfs(s);
    for(int i = 1; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
}

void graf :: sortare_topologica()
{
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    fout << "\n";
}

void graf :: componente_tare_conexe() // kosaraju
{
    int top;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    viz.reset();
    while(!s.empty())
    {
        top = s.top();
        s.pop();
        if(!viz[top])
        {
            k++;
            dfsctc(top);
        }
    }

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : ctc[i])
            fout << j << " ";
        fout<<"\n";
    }
}

void graf :: dfs_biconex(int nod, int tata)
{
    viz[nod] = 1;
    s_biconex.push(nod);

    mic[nod] = nivel[nod] = nivel[tata] + 1;

    for(auto i : h[nod])
    {
        if(i != tata)
        {
            if(viz[i])
                mic[nod] = min(mic[nod], nivel[i]);
            else
            {
                dfs_biconex(i, nod);

                mic[nod] = min(mic[nod], mic[i]);

                if(nivel[nod] <= mic[i]) // o noua componenta biconexa
                {
                    k++;
                    while(s_biconex.top() != i)
                    {
                        cbiconexe[k].push_back(s_biconex.top());
                        s_biconex.pop();
                    }
                    s_biconex.pop();
                    cbiconexe[k].push_back(i);
                    cbiconexe[k].push_back(nod);
                }
            }
        }
    }
}

void graf :: componente_biconexe()
{
    nivel[0] = 0;
    dfs_biconex(1, 0);

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : cbiconexe[i])
            fout << j << " ";
        fout<<"\n";
    }
}

void graf :: havel_hakimi()
{
    int lg, x, suma = 0;
    vector<int>v;
    fin >> lg;
    for(int i = 1; i <= lg; i++)
    {
        fin >> x;
        v.push_back(x);
        suma += x;
    }

    if(suma % 2 == 1)
    {
        fout << "Nu\n";
        return;
    }

    while(true)
    {
        if(v.size() == 0)
        {
            fout << "Da\n";
            return;
        }
        sort(v.begin(), v.end(), greater<int>());
        x = v[0];

        if((int)v.size() - 1 < x)
        {
            fout << "Nu\n";
            return;
        }
        for(int i = 1; i < x + 1; i++)
        {
            v[i]--;
            v[i - 1]= v[i];

            if(v[i] < 0)
            {
                fout << "Nu\n";
                return;
            }
        }
        v.pop_back();
    }
}

/*void graf :: muchii_critice(int nod, int tata, vector< vector<int> >& h2)
{
    viz[nod] = 1;

    mic[nod] = nivel[nod] = nivel[tata] + 1;

    for(int i = 0; i < h2[nod].size(); i++)
    {
        int vecin = h2[nod][i];

        if(!viz[vecin])
        {
            muchii_critice(vecin, nod, h2);

            mic[nod] = min(mic[nod], mic[vecin]);

            if(nivel[nod] < mic[vecin])
            {
                vector<int> muchie = {nod, vecin};
                muchii.push_back(vector<int>{nod, vecin});
            }
        }
        else if(vecin != tata)
        {
            mic[nod] = min(mic[nod], nivel[vecin]);
        }
    }
}

vector<vector<int>> graf :: criticalConnections(int n, vector<vector<int>>& connections)
{
    vector< vector<int> > h2(100003);
    for(int i = 0; i < connections.size(); i++)
    {
        h2[connections[i][0]].push_back(connections[i][1]);
        h2[connections[i][1]].push_back(connections[i][0]);
    }
    muchii_critice(1, 0, h2);
    return muchii;
}*/
///---------------------------------------------------------------------------------------------

void graf :: Union(int x, int y, vector<int> &t)
{
    t[y] = x;
}

int graf :: Find(int x, vector<int> &t)
{
    int rad, y;
    rad = x;
    while(t[rad] != 0)
        rad = t[rad];

    while(x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

int graf :: kruskal(int &n, int &m, vector<tuple<int, int, int, bool>> &muchii_cost, vector<int> &t)
{
    int costmin, nrcc, x, y;
    sort(muchii_cost.begin(), muchii_cost.end(),
        [](const tuple<int, int, int, bool> &A, const tuple<int, int, int, bool> &B) -> bool { return COST(A) < COST(B); });

    nrcc = n;
    costmin = 0;
    for(int i = 0; i < m && nrcc > 1; i++)
    {
        x = Find(X(muchii_cost[i]), t);
        y = Find(Y(muchii_cost[i]), t);
        if(x != y)
        {
            VIZ(muchii_cost[i]) = true;
            costmin += COST(muchii_cost[i]);
            Union(x, y, t);
            nrcc--;
        }
    }

    return costmin;
}

void graf :: apm()
{
    vector<int> t(nmax);
    for(int i = 0; i <= nmax - 3; i++)
        t[i] = 0;

    fout << kruskal(n, m, muchii_cost, t) << "\n";


    int cnt;
    cnt = 0;
    for(int i = 0; i < m; i++)
        if(VIZ(muchii_cost[i]) == true)
            cnt++;
    fout << cnt << "\n";

    for(int i = 0; i < m; i++)
        if(VIZ(muchii_cost[i]) == true)
            fout << X(muchii_cost[i]) << " " << Y(muchii_cost[i]) << "\n";
}

void graf :: dijkstra(int &start, vector<int> &d, vector<bool> &viz_coada)
{
    int k;
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > coada_muchii;
    coada_muchii.push({d[start], start});

    while(!coada_muchii.empty())
    {
        k = coada_muchii.top().second;
        coada_muchii.pop();
        viz_coada[k] = false;

        for (auto w : graf_cost[k])
        {
            if(d[w.first] > d[k] + w.second)
            {
                d[w.first] = d[k] + w.second;

                if(!viz_coada[w.first])
                {
                    coada_muchii.push({d[w.first], w.first});
                    viz_coada[w.first] = true;
                }
            }
        }
    }
}

void graf :: pb_dijkstra(int start)
{
    vector<int> d(nmax);
    vector<bool> viz_coada(nmax);

    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    d[start] = 0; // de la nodul 1 plec

    dijkstra(start, d, viz_coada);
    for(int i = 2; i <= n; i++)
        if(d[i] == 1e9) fout << "0 ";
        else fout << d[i] << " ";
    fout << "\n";
}

int main()
{
    /// dijkstra
    int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie(x, y, cost);
    }
    g.pb_dijkstra(1);


    /// apm
    /*int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie(x, y, cost);
    }
    g.apm();*/


    /// dfs
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_conexe();*/

    /// bfs
    /*int n, m, s, x, y;

    fin >> n >> m >> s;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.distante(s);*/

    /// biconex
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_biconexe();*/

    /// ctc
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_tare_conexe();*/

    /// sortare topologica
    /*int n, m, s, x, y;

    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.sortare_topologica();*/

    /// havel hakimi
    //graf::havel_hakimi();

    /// muchii critice [[0,1],[1,2],[2,0],[1,3]]
    //graf::criticalConnections(..);


    fin.close();
    fout.close();
    return 0;
}