#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,costmin;
vector<pair<int,int> >L[200002],rasp;
int dist[200002],t[200002];
bitset <200002> viz;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        fin>>x>>y>>c;
        L[x].push_back({y,c});
        L[y].push_back({x,c});
    }
}

void Prim()
{
    priority_queue< pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > >pq;

    for(int i=1;i<=n;++i)
        dist[i]=2e9;
    dist[1]=0;
    pq.push({0,1});

    while(!pq.empty())
    {
        int nod=pq.top().second;
        pq.pop();
        if(viz[nod]==1)
            continue;
        costmin+=dist[nod];
        viz[nod]=1;
        if(t[nod] != 0)
            rasp.push_back({nod,t[nod]});
        for(auto it : L[nod])
        {
            if(viz[it.first]==0 && dist[it.first]>it.second)
            {
                dist[it.first]=it.second;
                pq.push({it.second,it.first});
                t[it.first]=nod;
            }
        }
    }
    fout<<costmin<<'\n';
    fout<<rasp.size()<<'\n';
    for(auto it : rasp)
        fout<<it.first<<' '<<it.second<<'\n';
}

int main()
{
    citire();
    Prim();
}