#include<bits/stdc++.h>
#define Nmax 200020
#define inf 200000020
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <pair <int,int> > Edges[Nmax],coada;
bool comp(pair<int,int> A, pair <int,int> B)
{
    return A.second>B.second;
}
int tata[Nmax],verif[Nmax],viz[Nmax],i,n,m,cost,x,y,c;
void prim()
{
    int next,c;
    for(int i=2; i<=n; ++i)
        verif[i]=inf;
    coada.push_back({1,0});
    tata[1]=0;
    while(coada.size()!=0)
    {
        int nod=coada.front().first;
        int cost=coada.front().second;
        pop_heap(coada.begin(),coada.end(),comp);
        coada.pop_back();
        viz[nod]=1;
        for(int i=0; i<Edges[nod].size(); ++i)
        {
              pair<int,int> e=Edges[nod][i];
              next=e.first;
              c=e.second;
              if(verif[next]>c && viz[next]==0)
              {
                  verif[next]=c;
                  tata[next]=nod;
                  coada.push_back({next,c});
                  push_heap(coada.begin(),coada.end(),comp);
              }
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        Edges[x].push_back({y,c});
        Edges[y].push_back({x,c});
    }
    prim();
    for(i=1; i<=n; ++i)
        cost += verif[i];
    g<<cost<<'\n'<<n-1<<'\n';

    for(i=2; i<=n; ++i)
        g<<i<<' '<<tata[i]<<'\n';
    return 0;
}