#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,int> > ADJ[400005]; ///vecin,cost

priority_queue<pair<int,pair<int,int> > > H; ///cost, varf,parinte

int n,m,total;

int C[400005],P[400005];

int main()
{
    fin >> n >> m;
    int i;
    for (i=1;i<=m;++i)
    {
        int a,b,c;
        fin >> a >> b >> c;
        ADJ[a].push_back({b,c});
        ADJ[b].push_back({a,c});
    }
    H.push({0,{1,0}});
    while (!H.empty())
    {
        pair<int,pair<int,int> > p;
        p=H.top();
        H.pop();
        int v=p.second.first;
        if (C[v]==0)
        {
            C[v]=1;
            P[v]=p.second.second;
            total-=p.first;
            ///toti vecinii neclasificati ai lui v sunt depusi in H
            vector<pair<int,int> > :: iterator it;
            for (it=ADJ[v].begin();it!=ADJ[v].end();++it)
            {
                int w=(*it).first;
                if (C[w]==0)
                {
                    H.push({-(*it).second,{w,v}});
                }
            }
        }
    }
    fout << total << '\n' << n-1 << '\n';
    for (i=2;i<=n;++i)
    {
        fout << i << " " << P[i] << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}