#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 200005
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
vector<pair<int,int>> V[nmax];
int d[nmax],tata[nmax],n,m,apm;
bool viz[nmax];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
        V[b].push_back(make_pair(a,c));
    }
    heap.push(make_pair(d[1],1));
    for(int i=2;i<=n;i++)
        d[i]=inf;
    while(!heap.empty()) {
        int sursa = heap.top().second;
        viz[sursa] = true;
        heap.pop();
        for (auto a: V[sursa]) {
            if (!viz[a.first]) {
                if (a.second < d[a.first]) {
                    d[a.first] = a.second;
                    tata[a.first] = sursa;
                    heap.push(make_pair(d[a.first], a.first));
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        apm+=d[i];
    g<<apm<<endl<<n-1<<endl;
    for(int i=2;i<=n;i++)
        g<<i<<" "<<tata[i]<<'\n';
    f.close();
    g.close();
    return 0;
}