#include <bits/stdc++.h>
#define int long long
#define dim 200002
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
int viz[dim],tata[dim];

struct el
{
    int nod,c,from;
    bool operator < (const el &A) const
    {
        return c>A.c;
    }
};
vector<el>a[dim];
priority_queue<el>pq;

void apm ()
{
    int cm=0;
    pq.push({1,0,0});
    while (!pq.empty())
    {
        int  x=pq.top().nod;
        if (viz[x]==0)
        {
            viz[x]=1;
            tata[x]=pq.top().from;
            cm+=pq.top().c;
            pq.pop();
            for (auto y:a[x])
                if (viz[y.nod]==0)
                    pq.push({y.nod,y.c,x});
        }
        else    pq.pop();
    }
    fout<<cm<<'\n';
}

int32_t main()
{
    int n,m,x,y,z,i;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        a[x].push_back({y,z,0});
        a[y].push_back({x,z,0});
    }
    apm();
    fout<<n-1<<'\n';
    for (i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';
    return 0;
}