#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream gout("dijkstra.out");

class Graf
{
    private:
    int noduri;
    vector< pair< pair <int, int>, int> > lista_muchii;
    vector< vector<pair<int, int> > > lista_ad;
    priority_queue <pair<int, int>, vector <pair<int,int> >, greater <pair<int,int> > > coada;
    vector<int> Dist;
    vector< int > reprez;
    vector< int > dim;
    vector< pair<int, int> > rez;
    int muchii = 0;
public:
    Graf ();
    Graf (int noduri);
    void citire_graf(int m);
    void APM();
    void unite(int x, int y);
    int Find(int x);
    void Disjoint(int x, int y, int op);
    void unite_disjoint(int n1, int n2);
    void initializare_vectori(int m);
    void citire_Dijkstra(int m);
    void Dijkstra();

};

Graf :: Graf ()
{
    vector< pair< pair <int, int>, int> > aux;
    noduri = 0;
    lista_muchii =  aux;

}
Graf :: Graf (int n)
{
    noduri = n;
    lista_ad.resize(n+1);
}
void Graf :: citire_graf (int muchii)
{
    int x,y,c;
    for ( int i = 1; i <= muchii; i++ )
    {
        cin >> x >> y >>c;
        lista_muchii.push_back(make_pair(make_pair(x,y),c));
    }
}
int Graf :: Find(int x) {
    if(x == reprez[x])
        return x;
    return Find(reprez[x]);

}


bool SorteazaDupaCost(const pair< pair<int,int>, int> &a,
                    const pair< pair<int,int>, int> &b)
{
    return (a.second < b.second);
}

void Graf:: unite(int nod1,int nod2)
{
    int x = Graf::Find(nod1);
    int y = Graf::Find(nod2);

    if (dim[x] >= dim[y])
    {
    reprez[y] = x;
    dim[x] += dim[y];
    muchii++;
    }
    else
    {
        reprez[x] = y;
        dim[y] += dim[x];
        muchii++;
    }

}

void Graf:: unite_disjoint(int nod1,int nod2)
{
    int x = Graf::Find(nod1);
    int y = Graf::Find(nod2);

    if (dim[x] >= dim[y])
    {
    reprez[y] = x;
    dim[x] += dim[y];
    muchii++;
    }
    else
    {
        reprez[x] = y;
        dim[y] += dim[x];
        muchii++;
    }

}

void Graf :: APM()
{   int suma_cost = 0;
    muchii = 0;
    reprez.resize(noduri+1);
    dim.resize(noduri+1);
    for(int i = 1; i <= noduri; i++)
        {reprez[i] = i;
        dim[i] = 1;
        }
    sort(lista_muchii.begin(), lista_muchii.end(),SorteazaDupaCost);
    for (int i = 0; i < lista_muchii.size(); i++)
        {   int x = lista_muchii[i].first.first;
            int y =  lista_muchii[i].first.second;
            if(Find(x) != Find(y))
           {
               rez.push_back(make_pair(y, x));
               unite(y,x);
            suma_cost+= lista_muchii[i].second;
           }}
    gout<<suma_cost<<'\n';
    gout<<muchii<<'\n';
    for(int i = 0; i< muchii; i++)
        gout<<rez[i].first << ' ' << rez[i].second<<'\n';

}

void Graf::initializare_vectori(int n)
{
    reprez.resize(noduri+1);
    dim.resize(noduri+1);
    for(int i = 1; i <= n; i++)
        {reprez[i] = i;
        dim[i] = 1;
        }
}
void Graf:: Disjoint(int x, int y, int op)
{
        if(op == 1)
            unite(x,y);
        else
            {if(Find(x) == Find(y))
                gout<<"DA"<<'\n';
            else gout<<"NU"<<'\n';
                }
        }

void Graf::citire_Dijkstra(int muchii)
{
     int x,y,c;
    for ( int i = 1; i <= muchii; i++ )
    {
        cin >> x >> y >>c;
        lista_ad[x].push_back(make_pair(y,c));
    }
}

void Graf::Dijkstra()
{
    vector<bool> parcurs;
    parcurs.resize(noduri+1);
    coada.push(make_pair(0,1));
    Dist.resize(noduri+1);
    for(int i = 1; i<= noduri;i++)
    {
        Dist[i] = 10000000;
        parcurs[i] = 0;
    }
    Dist[1] = 0;
    while (!coada.empty())
    {
        int curr = coada.top().second;
        if(parcurs[curr == 1])
            continue;
         parcurs[curr] = 1;
         coada.pop();


        for(int i = 0; i < lista_ad[curr].size();i++)
            {
                if(Dist[curr] + lista_ad[curr][i].second < Dist[lista_ad[curr][i].first])
                {

                    Dist[lista_ad[curr][i].first]=Dist[curr]+lista_ad[curr][i].second;
                    coada.push(make_pair(Dist[lista_ad[curr][i].first],  lista_ad[curr][i].first));

                }
            }
    }
    for(int i = 2; i <= noduri; i++)
        gout<<Dist[i]<<' ';


}
int main()
{
    int n,m;
    fin>>n>>m;
    Graf g(n);
    g.citire_Dijkstra(m);
    g.Dijkstra();

    return 0;
}