#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int INF=1e9;
struct muchie
{
    int cost,nod;
    bool operator<(const muchie& a) const{
        return cost>a.cost;
    }
};
vector<muchie> v[200001];
priority_queue<muchie> pq;
bool aux[200001];
int cmin[200001];
int tata[200001];
int main()
{
    int n,m,ans=0;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cmin[i]=INF;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    pq.push({0,1});
    cmin[1]=0;
    while(!pq.empty())
    {
        int cost=pq.top().cost;
        int node=pq.top().nod;
        pq.pop();
        if(aux[node]) continue;
        aux[node]=1;
        ans+=cost;
        for(auto it:v[node])
        {
            int cost1=it.cost;
            int node1=it.nod;
            if(aux[node1]) continue;
            if(cmin[node1]>cost1)
            {
                cmin[node1]=cost1;
                tata[node1]=node;
                pq.push({cost1,node1});
            }
        }
    }
    fout<<ans<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
    {
        fout<<tata[i]<<' '<<i<<'\n';
    }
    return 0;
}