#include <bits/stdc++.h>
#define inf 0x3F3F3F3F
#define pi pair<int,int>
#define nmax 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,sol;
int d[nmax],viz[nmax],t[nmax];
vector<pi>L[nmax];
priority_queue<pi,vector<pi>,greater<pi>>pq;
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        L[x].push_back({y,cost});
        L[y].push_back({x,cost});
    }
    for(int i=1; i<=n; i++)
    {
        d[i]=inf;
        t[i]=-1;
    }
    t[1]=0;
    d[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        int dist_curenta=pq.top().first;
        int nod_curent=pq.top().second;
        pq.pop();
        if(viz[nod_curent]==1)
            continue;
        viz[nod_curent]=1;
        sol+=dist_curenta;
        for(auto i:L[nod_curent])
            if(d[i.first]>i.second && viz[i.first]==0)
            {
                d[i.first]=i.second;
                t[i.first]=nod_curent;
                pq.push({d[i.first],i.first});
            }
    }
    fout<<sol<<'\n';
    fout<<n-1<<'\n';
    for(int i=2; i<=n; i++)
            fout<<i<<' '<<t[i]<<'\n';

    return 0;
}