#include <bits/stdc++.h>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

//kruskal

int find(int nod, vector<int>& p)
{
    while(nod != p[nod])
        nod = p[nod];

    return nod;
}

void uNion(int comp1, int comp2, vector<int>& p, vector<int>& h)
{
    comp1 = find(comp1, p);
    comp2 = find(comp2, p);

    if(h[comp1] < h[comp2]) 
        p[comp1] = comp2;
    else 
        if(h[comp1] > h[comp2])
            p[comp2] = comp1;
        else 
            {
                p[comp1] = comp2;
                h[comp2] ++;
            }
}

void kruskal()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    struct Trio{int x, y, z;};

    vector<Trio> muchii;

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;

        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }

    sort(muchii.begin(), muchii.end(), [] (const Trio& a, const Trio& b) {
	return a.z < b.z;
	});

    vector<int> p(n + 1);

    for(int i = 1; i <= n; i ++)
        p[i] = i;

    vector<int> h(n + 1, 1);

    int sol = 0;
    vector<pair<int, int>> muchii_sol;

    for(auto elem: muchii)
    {
        if(find(elem.x, p) != find(elem.y, p))
        {
            sol += elem.z;
            muchii_sol.push_back({elem.x, elem.y});
            uNion(elem.x, elem.y, p, h);
        }
    }

    fout << sol << '\n' << muchii_sol.size() << '\n';

    for(auto m: muchii_sol)
    {
        fout << m.first << ' ' << m.second << '\n';
    }

}

void prim()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    
    fin >> n >> m;

    vector<int> d (n + 1, 1e9);
    d[1] = 0;

    vector<pair<int, int>> L[n + 1];
    vector<pair<int, int>> muchii_sol;

    vector<int> viz(n + 1, 0);
    vector<int> p(n + 1);
    for(auto i: p)
        p[i] = i;

    int sol = 0;

    priority_queue<pair<int, int>> pq;

    pq.push({-d[1], 1});

    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        fin >> x >> y >> z;

        L[x].push_back({y, z});
        L[y].push_back({x, z});
    }

    while(pq.size() > 0)
    {
        int cost = pq.top().first; 
        int nod = pq.top().second;
        pq.pop();

        if(viz[nod] != 1)
        {
            viz[nod] = 1;
            sol += cost;
            if(nod != 1)muchii_sol.push_back({nod, p[nod]});
            for(auto m: L[nod])
            {
                if(d[m.first] >m.second)
                {
                    d[m.first] = m.second;
                    pq.push({-d[m.first], m.first});
                    p[m.first] = nod;
                }
            }
        }
    }

    fout << (-1)*sol << '\n' << muchii_sol.size() << '\n';

    for(auto m: muchii_sol)
        fout << m.first << ' ' << m.second << '\n';
}

void retea2()
{
    ifstream fin("retea2.in");
    ofstream fiut("retea2.out");

    vector<pair<int, int>> centrale;
    vector<pair<int, int>> blocuri;

    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
        {
            int x, y;
            cin >> x >> y;
            centrale.push_back({x, y});
        }

    for(int i = 1; i <= m; i ++)
        {
            int x, y;
            cin >> x >> y;
            blocuri.push_back({x, y});
        }
}

int main()
{
    prim();
    return 0;
}