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

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

vector <pair<int,int>> G[200000];
int Afisare[200000];

int n,m,x,y,c,S;
vector<int> T,D;
vector<bool>V;

void Prim()
{

    priority_queue <
    pair<int , int>  ,
    vector<pair<int , int>> ,
    greater<pair<int , int>>
    >Q;
    V[1] = true;
    T[1] = 0;
    D[1] = 0;

    for(auto x : G[1])
    {
        T[x.second] = 1;
        D[x.second] = x.first;
        Q.push(x);
    }
    for(int k = 1 ; k < n ; k++)
    {
        pair<int , int> P;
        do{
            P = Q.top();
            Q.pop();
        }while(V[P.second]);

        V[P.second] = true;
        S += P.first;
        int a=P.second;
        int b=T[a];
        Afisare[a]=b;

        for(auto x : G[P.second])
            if(V[x.second] == false && D[x.second] > x.first)
            {
                T[x.second] = P.second;
                D[x.second] = x.first;
                Q.push(x);
            }
    }
}

int main()
{
    for(fin >> n >> m ; m ; --m)
    {
        fin >> x >> y >> c;
        G[x].push_back({c , y});
        G[y].push_back({c , x});
    }

    V.resize(n + 1 , false);
    T.resize(n + 1 , -1);
    D.resize(n + 1 , 0x3f3f3f3f);
    Prim();
    fout<<S<<endl;
    fout<<n-1<<endl;
    for(int i=1;i<=n;i++)
        if(Afisare[i])
            fout<<i<<" "<<Afisare[i]<<endl;
    return 0;
}