#include<bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,int>>v[200001];
int d[200001],inarb[200001],pred[200001];
const int INF=1e9+7;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>h;
int main()
{
    int n,m,i,a,b,c,ct=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    for(i=2;i<=n;i++)
        d[i]=INF;
    h.push({0,1});
    while(!h.empty())
    {
        pair<int,int>nod=h.top();
        h.pop();
        int x=nod.second;
        if(inarb[x])
        {
            continue;
        }
        inarb[x]=true;
        ct+=nod.first;
        for(auto q:v[x])
            if(!inarb[q.second])
            {
                if(d[q.second]>q.first)
                {
                    d[q.second]=q.first;
                    h.push({d[q.second],q.second});
                    pred[q.second]=x;
                }
            }
    }
    fout<<ct<<"\n"<<n-1<<"\n";
    for(int i=2;i<=n;i++)
        fout<<i<<" "<<pred[i]<<"\n";
}