#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
//KRUSKAL
// struct Muchie {
//     int x;
//     int y;
//     int cost;
// };
// int n,m,x,y,cost,s,nr,c;
// vector<int>t(200001,0);
// vector<int>h(200001,1);
// vector<Muchie>v,rez;
// bool cmp(Muchie a, Muchie b) {
//     return a.cost<b.cost;
// }
// int Find(int x){
//     while(t[x]!=x){
//         x=t[x];
//     }
//     return x;
// }
// void Union(int x, int y)
// {
//     x=Find(x);
//     y=Find(y);
//     if(x!=y){
//         if(h[x]<h[y])
//             t[x]=y;
//         else if(h[x]>h[y])
//             t[y]=x;
//         else{
//             t[y]=x;
//             h[x]++;
//         }
//     }
// }
// int main()
// {
//     f>>n>>m;
//     for(int i=1;i<=m;i++){
//         f>>x>>y>>c;
//         v.push_back({x,y,c});
//     }
//     for(int i=1;i<=n;i++)
//         t[i]=i;
//     sort(v.begin(),v.end(),cmp);
//     for(auto muchie:v){
//         if(Find(muchie.x)!=Find(muchie.y))
//         {
//             cost+=muchie.cost;
//             nr++;
//             s+=muchie.cost;
//             rez.push_back(muchie);
//             Union(muchie.x,muchie.y);
//         }
//     }
//     g<<s<<"\n"<<nr<<"\n";
//     for(auto muchie:rez){
//         g<<muchie.x<<" "<<muchie.y<<"\n";
//     }
//     return 0;
// }
//PRIM
int main()
{
    vector<int>dist(200001,1e9);
    vector<bool>viz(200001,false);
    vector<int>parent(200001,0);
    vector<pair<int,int>>adj[200001];
    priority_queue<pair<int,int>>pq;
    int n,m,x,y,cost,s,nr,c;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    dist[1]=0;
    pq.push({0,1});  
    while(!pq.empty())
    {
        int nod=pq.top().second;
        pq.pop();
        if(viz[nod])continue;
        cost+=dist[nod];
        viz[nod]=true;
        for(auto it:adj[nod]){
            int vecin=it.first;
            int cost=it.second;
            if(!viz[vecin]&&cost<dist[vecin]){
                dist[vecin]=cost;
                parent[vecin]=nod;
                pq.push({-cost,vecin});
            }
        }
    }
    g<<cost<<"\n";
    g<<n-1<<"\n";
    for(int i=2;i<=n;i++){
        g<<i<<" "<<parent[i]<<"\n";
    }
    return 0;
}