#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;
const int N = 200001;
const int INF = (N - 1) * 1001;
int n, m;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<vector<pair<int, int>>> G(N + 1);
vector<int> D(N + 1, INF);
vector<int> tata(N + 1, 0);

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

}

int COST = 0;
vector<bool> viz(N + 1, false);
vector<pair<int, int>> sol;

//O(n*log(n))
void PrimHeap(int s)
{
    int k = 0;
    D[s] = 0;
    set<pair<int, int>> Q;
    Q.insert({D[s], s});
    while (!Q.empty())
    {
        auto el = (*Q.begin());
        Q.erase(Q.begin());
//        if(!viz[el.second]) {
            viz[el.second] = true;
            COST+= el.first;
            for (auto v:G[el.second])
                if (v.second < D[v.first] && !viz[v.first])
                {
                	Q.erase({D[v.first],v.first});
                    D[v.first] = v.second;
                    tata[v.first] = el.second;
                    Q.insert({v.second, v.first});
                    k++;
                }
//        }
    }
    fout << COST << "\n" << n-1 << "\n";
    for(int i = 1; i <= n; i++)
        if(tata[i] != 0)
            fout << tata [i] << " " << i << "\n";

}

//O(n^2)
void Prim(int s)
{
    D[s] = 0;
    viz[s] = true;
    for(auto el:G[s])
        D[el.first] = el.second;
    for (int i = 1; i < n; i++)
    {
        int poz = -1, min = INF + 1;
        for (int j = 1; j <= n; j++)
            if (D[j] < min && !viz[j]) poz = j, min = D[j];
        if (poz > -1)
        {

            viz[poz] = true;
            for (auto v:G[poz])
                if ( !viz[v.first] && v.second < D[v.first])
                {
                    D[v.first] = v.second;
                    tata[v.first] = poz;
                }
        }
    }
    for(int i=1;i<=n;i++)
        COST+=D[i];
    fout<<COST<<'\n'<<n-1<<'\n';
    for(int i=1;i<=n;i++)
        if(tata[i]!=0) fout<<tata[i]<<" "<<i<<'\n';

}

int main()
{
    citire();
    PrimHeap(1);
    return 0;
}