//O(n ^ 2) pt grafuri dense
#include <bits/stdc++.h>

std :: ifstream in ("apm.in");

std :: ofstream out ("apm.out");

const int NMAX = 1e3 + 5;

const int INF = 2e9;

int n;

int m;

int x;

int y;

int sum;

int d;

int a[NMAX][NMAX];

std :: bitset <NMAX> visited;

std :: pair <int, int> dist[NMAX];

std :: stack <std :: pair <int, int>> s;

void prim()
{
    for(int i = 1; i <= n; i ++)
    {
        dist[i].first = INF;
    }

    dist[1].first = 0;

    for(int i = 1; i <= n; i ++)
    {
        int poz = 0;

        for(int j = 1; j <= n; j ++)
        {
            if(visited[j] == false && (!poz || dist[j].first < dist[poz].first))
            {
                poz = j;
            }
        }

        visited[poz] = true;

        sum += dist[poz].first;

        if(dist[poz].second != 0)
        {
            s.push(std :: make_pair(dist[poz].second, poz));
        }

        for(int i = 1; i <= n; i ++)
        {
            if(a[poz][i] < dist[i].first)
            {
                dist[i].first = a[poz][i];

                dist[i].second = poz;
            }
        }
    }

    out << sum << '\n';

    out << n - 1 << '\n';

    while(!s.empty())
    {
        out << s.top().first << " " << s.top().second << '\n';

        s.pop();
    }
}

int main()
{

    in >> n >> m;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            a[i][j] = INF;
        }
    }

    for(int i = 1; i <= m; i ++)
    {
        in >> x >> y >> d;

        a[x][y] = d;

        a[y][x] = d;
    }

    prim();

    return 0;
}