#include <bits/stdc++.h>
#define pi pair < int , pair < int , int > >
#define F first
#define S second
using namespace std;
int n, m , i , x , y , c , nod , f[200005] , cost;
vector < pair <int , int > > ans , g[200005];
priority_queue < pi , vector <pi> , greater <pi> > Q;
pi per;
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
    Q.push({ 0, {0 , 1}});
    while(!Q.empty())
    {
        per = Q.top();
        Q.pop();
        nod = per.S.S;
        if(f[nod] == 1)continue;
        ans.push_back({per.S.F , per.S.S});
        f[nod] = 1;
        for(i=0;i<g[nod].size(); i++)
            if(f[g[nod][i].F] == 0)Q.push({g[nod][i].S ,{nod , g[nod][i].F} });
        cost += per.F;
    }
    fout << cost << "\n";
    fout << n - 1 <<"\n";
    for(i=1; i<n; i++)
    {
        fout << ans[i].F <<  " " << ans[i].S << "\n";
    }
    return 0;
}