#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
 
#define NMAX 200005
#define MMAX 400005
 
using namespace std;
 
int t, n, m, i, k, x, y, c, sum, sel, s1, s2;
pair<pair<int, int>, int> M[MMAX];
int T[NMAX], R[NMAX];
bool good[MMAX];
 
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
    return a.second < b.second;
}
 
int anc(int x)
{
    int ret = x, aux;
    while (T[ret] != ret)
        ret = T[ret];
    while (x != ret)
    {
        aux = T[x];
        T[x] = ret;
        x = aux;
    }
    return ret;
}
 
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
     
    int t = 1;
    while (t--)
    {
        f >> n >> m;
        if (m < n - 1)
        {
            g << -1 << '\n';
            continue;
        }
	      if (n == 1)
        {
            g << M[0].second << '\n';
            continue;
        }
        for (i = 1; i <= n; ++i)
        {
            T[i] = i;
            R[i] = 1;
        }
        for (i = 0; i < m; ++i)
        {
            f >> x >> y >> c;
            M[i] = make_pair(make_pair(x, y), c);
        }
        sort(M, M + m, comp);
      
        sum = 0;
        sel = 0;
        for (i = 0; sel < n - 1 && i < m; ++i)
        {
            s1 = anc(M[i].first.first);
            s2 = anc(M[i].first.second);
            if (s1 != s2)
            {
                if (R[s1] > R[s2])
                    T[s2] = s1;
                else if (R[s1] < R[s2])
                    T[s1] = s2;
                else
                {
                    T[s2] = s1;
                    ++R[s1];
                }
                sum += M[i].second;
                ++sel;
                good[i] = 1;
            }
        }

        if(i == m && sel != n - 1)
          g << -1 << '\n';
        else
          g << sum << '\n';
        g << n - 1 << '\n';
        for(i = 0; i < m; i++)
          if(good[i])
            g  << M[i].first.first << ' ' << M[i].first.second << '\n';
    }
    g.close();
    f.close();
    return 0;
}