#include <bits/stdc++.h>

using namespace std;

#define TITLE "apm"

ifstream f (TITLE".in");
ofstream g (TITLE".out");

vector<pair<int,int>> Graph[200001];
vector<pair<int,int>> answer;

bitset<200001> Visited;

int n,m;

void Prim()
{
    long long Sum=0;
    priority_queue <pair<int,pair<int,int>>> PQ;
    for(auto it : Graph[1])
        PQ.push({it.first,{1,it.second}});
    Visited[1]=true;
    while(!PQ.empty())
    {
        int Node=PQ.top().second.second;
        int Cost=-PQ.top().first;
        PQ.pop();
        if(!Visited[Node])
        {
            Sum+=Cost;
            Visited[Node]=true;
            answer.push_back(PQ.top().second);
            for(auto it : Graph[Node])
                if(!Visited[it.second])
                PQ.push({it.first,{Node,it.second}});
        }
    }
    g<<Sum<<'\n'<<n-1<<'\n';
    for(auto it : answer)
        g<<it.first<<' '<<it.second<<'\n';
}

int main()
{
    f>>n>>m;
    while(m--)
    {
        int a,b,c;
        f>>a>>b>>c;
        c*=-1;
        Graph[a].push_back({c,b});
        Graph[b].push_back({c,a});
    }
    Prim();
    return 0;
}