#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,C[101],T[101],x,y,c,ctot;
bool apm[101];
struct muchie
{
    int nod, cost;
} a;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
int main()
{
    fin>>n>>m;
    vector<vector<muchie>> graf(n+1);
    for(int i=1;i<=n;i++)
        C[i]=INF;
    for(int k=1;k<=m;k++)
    {
        fin>>x>>y>>c;
        graf[x].push_back({y,c});
        graf[y].push_back({x,c});        
    }
    C[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        int v=pq.top().second;
        pq.pop();
        if(apm[v])
            continue;
        apm[v]=true;
        for(auto &M:graf[v])
            if(!apm[M.nod] && M.cost<C[M.nod])
            {
                C[M.nod]=M.cost;
                T[M.nod]=v;
                pq.push({C[M.nod],M.nod});
            }
    }
    for(int i=1;i<=n;i++)
        ctot+=C[i];
    fout<<ctot<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        fout<<T[i]<<' '<<i<<'\n';
    return 0;
}