#include <fstream>
#include <queue>
#include <vector>
#define INF 99999999
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct cmp{
    bool operator()(pair <int,int> x , pair <int,int> y){
        return x.second>y.second;}
        };
priority_queue < pair <int , int > , vector < pair <int,int> > ,cmp > heap;
int x,y,n,m,i,viz[200001],d[200001],nod,nr,cost,tata[200001],s;
vector < pair <int,int> > G[200001];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>cost;
        G[x].push_back(make_pair(y,cost));
        G[y].push_back(make_pair(x,cost));
    }
    for(i=1;i<=n;i++)
    d[i]=INF;
    d[1]=0;
    tata[1]=0;
    viz[1]=1;
    nr=1;

    for(i=0;i<G[1].size();i++)
    {
        d[G[1][i].first]=G[1][i].second;
        tata[G[1][i].first]=1;
        heap.push(G[1][i]);

    }
    while(nr!=n-1&&!heap.empty()){
        nod=heap.top().first;
        heap.pop();
        if(viz[nod]==1)
            continue;
           nr++;
                viz[nod]=1;
            for(i=0;i<G[nod].size();i++){
                if(d[G[nod][i].first]>G[nod][i].second&&viz[G[nod][i].first]==0){
                    d[G[nod][i].first]=G[nod][i].second;
                    tata[G[nod][i].first]=nod;
                    heap.push(G[nod][i]);
                }
            }
    }
for(i=1;i<=n;i++)
    s+=d[i];
g<<s<<'\n';
g<<n-1<<'\n';
for(i=2;i<=n;i++)
    g<<i<<" "<<tata[i]<<'\n';

    return 0;
}