#include <bits/stdc++.h>
#define NMAX 200010
#define inf 2047483646
using namespace std;

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

int n, m, cost;
typedef pair<int,int> pi;
vector <pi> G[NMAX], sol;
vector < pair<int, pi > > v;
int t[NMAX], h[NMAX];
bitset <NMAX> viz;

inline int unde(int a)
{
    int root = a;
    while(root != t[root])
        root = t[root];
    int aux = a;
    while(aux != root)
    {
        int next = t[aux];
        t[aux] = root;
        aux = next;
    }
    return root;
}

void inters(int x, int y)
{
    if(h[x] > h[y])
        t[y] = x;
    else{
        t[x] = y;
        if(h[x] == h[y])
            h[y]++;
    }
}
void kruskal()
{
    for(int i = 1; i <= n; ++i)
        t[i] = i;
    sort(v.begin(), v.end());
    for(auto it : v)
    {
        int a = it.second.first;
        int b = it.second.second;
        if(unde(a) != unde(b))
        {
            inters(unde(a), unde(b));
            cost += it.first;
            sol.push_back({a,b});
        }
    }
}

void prim()
{
    viz[1] = 1;
    set< pair<int, pi > > Q;
    for(auto it : G[1])
        Q.insert({it.second , {1, it.first} });

    while(!Q.empty() )
    {
        pair<int, pi > mch = *Q.begin();
        Q.erase(Q.begin());

        int a = mch.second.first;
        int b = mch.second.second;

        if(!viz[b])
        {
            viz[b] = 1;
            cost += mch.first;
            sol.push_back({a,b});
            for(auto it : G[b])
                Q.insert({it.second , {b, it.first} });


        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, z;
        f >> x >> y >> z;
        v.push_back({z, {x,y}});
        G[x].push_back({y,z});
        G[y].push_back({x,z});
    }
    //kruskal();
    prim();
    g << cost << '\n' << sol.size() << '\n';
    for(auto it : sol)
        g << it.first << ' ' << it.second << '\n';
    f.close();
    g.close();
    return 0;
}