#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=2e5, INF=1e9;
vector<pair<int,int> > mat[NMAX+5];
vector<int> dist(NMAX+5, INF), parent(NMAX+5);
vector<pair<int, int>> mst_edges;
vector<bool> used(NMAX+5);
int n, m, ans=0;
vector<pair<int,int> > answer;
void apm(int x){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    dist[x]=0;
    q.push({0,x});
    while(!q.empty()){
        int nod, edge_cost;
        edge_cost=q.top().first;
        nod=q.top().second;
        q.pop();
        if(!used[nod]){
            if(nod){
                ans+=edge_cost;
                answer.push_back({nod,parent[nod]});
            }
            for(auto it:mat[nod]){
                int cost=it.second, vecin=it.first;
                if(!used[vecin] and cost<dist[vecin]){
                    dist[vecin]=cost;
                    parent[vecin]=nod;
                    q.push({dist[vecin], vecin});
                }
            }
            used[nod]=1;
        }
    }

}
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, c;
        fin>>x>>y>>c;
        mat[x].push_back({y,c});
        mat[y].push_back({x,c});
    }
    apm(1);
    fout<<ans<<'\n'<<n-1<<'\n';
    for(auto it:answer){
        fout<<it.first<<' '<<it.second<<'\n';
    }
}