#include <bits/stdc++.h>

using namespace std;

bool comp(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
    if(a.first<b.first) return false;
    return true;
}

int n,m,x,y,z,cost,neg;
bool v[200005];
int p[200005];
vector <pair<int,int>> g[200005],f;
pair<int,pair<int,int>> mn;
priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,function<bool(pair<int,pair<int,int>>,pair<int,pair<int,int>>)>> q(comp);

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    mn={10000,{0,0}};
    for(int i=1;i<=m;i++){
        in >> x >> y >> z;
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
        if(z<mn.first) mn={z,{x,y}};
    }
    for(int i=1;i<=n;i++) p[i]=10000;
    p[mn.second.first]=mn.first;p[mn.second.second]=mn.first;
    //cout << p[mn.second.first] << ' ' << p[mn.second.second] << ' ' << mn.first << '\n';
    q.push(mn);
    while(q.size()){
        mn=q.top();
        q.pop();
        //cout << mn.second.first << ' ' << mn.second.second << '\n';
        //cout << p[mn.second.first] << ' ' << mn.first << '\n';
        if((!v[mn.second.first] && p[mn.second.first]==mn.first) || (!v[mn.second.second] && p[mn.second.second]==mn.first)){
            f.push_back({mn.second.first,mn.second.second});
            cost+=mn.first;
            if(!v[mn.second.first]){
                v[mn.second.first]=1;
                for(int i=0;i<g[mn.second.first].size();i++){
                    if(!v[g[mn.second.first][i].first] && p[g[mn.second.first][i].first]>g[mn.second.first][i].second) p[g[mn.second.first][i].first]=g[mn.second.first][i].second, q.push({g[mn.second.first][i].second,{mn.second.first,g[mn.second.first][i].first}});
                }
            }
            if(!v[mn.second.second]){
                v[mn.second.second]=1;
                for(int i=0;i<g[mn.second.second].size();i++){
                    if(!v[g[mn.second.second][i].first] && p[g[mn.second.second][i].first]>g[mn.second.second][i].second) p[g[mn.second.second][i].first]=g[mn.second.second][i].second, q.push({g[mn.second.second][i].second,{mn.second.second,g[mn.second.second][i].first}});
                }
            }
        }
        if(f.size()==n-1){
            out << cost << '\n' << f.size() << '\n';
            for(int i=0;i<f.size();i++){
                out << f[i].first << ' ' << f[i].second << '\n';
            }
            return 0;
        }
    }
    out << cost << '\n' << f.size() << '\n';
    for(int i=0;i<f.size();i++){
        out << f[i].first << ' ' << f[i].second << '\n';
    }
}