#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector <pair <int, int> > v[200005];
vector <pair <int, int> > c[200005];
int viz[200005];

struct st{
    int a;
    int b;
    int c;
    bool operator<(const st& other) const {
        return c > other.c;
    }
};
priority_queue <st> q;
vector <st> rez;
int main()
{
    int n, m;
    in >> n >> m;
    int start = 0;
    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        in >> a >> b >> c;
        if(i == 1)
            start = a;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    for(int i = 0; i < v[start].size(); i ++)
    {
        st xd;
        xd.a = start;
        xd.b = v[start][i].first;
        xd.c = v[start][i].second;
        q.push(xd);
    }
    viz[start] = 1;
    int cnt = 0;
    int s = 0;
    while(cnt < n - 1)
    {
        st x = q.top();
        q.pop();
        if(viz[x.b] == 0)
        {
            cnt = cnt + 1;
            s = s + x.c;
            viz[x.b] = 1;
            rez.push_back(x);
            for(auto it : v[x.b])
            {
                if(viz[it.first] == 0)
                {
                    st xd;
                    xd.a = x.b;
                    xd.b = it.first;
                    xd.c = it.second;
                    q.push(xd);
                }
            }
        }
    }
    out << s << '\n' << n - 1 << '\n';
    for(auto it : rez)
        out << it.b << " " << it.a << '\n';
    return 0;
}