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

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

struct DSU
{
    vector<int>father;
    vector<int>sz;
    
    DSU(int n)
    {
        father.resize(n + 1);
        sz.resize(n + 1);
        
        for(int i = 1; i <= n; ++ i)
        {
            father[i] = i;
            sz[i] = 1;
        }
    }
    
    inline int FindFather(int x)
    {
        if(father[x] == x)
            return x;
        return father[x] = FindFather(father[x]);
    }
    
    inline void Join(int x, int y)
    {
        int father_x = FindFather(x);
        int father_y = FindFather(y);
        
        if(father_x == father_y)
            return;
        
        if(sz[father_x] > sz[father_y])
            swap(father_x, father_y);
            
        father[father_x] = father_y;
        sz[father_y] += sz[father_x];
    }
    
    inline bool SameSet(int x, int y)
    {
        return FindFather(x) == FindFather(y);
    }
};

struct TRIO
{
    int x, y, cost;    
};

const int NMAX = 1e5+5;
int n, m, cost, nr_muchii;
vector<TRIO>graph;
vector<pair<int,int>>ans;
DSU dsu(NMAX);

inline bool compare(const TRIO &x, const TRIO &y)
{
    return x.cost < y.cost;
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    
    fin >> n >> m;
    
    for(int i = 1; i <= m; ++ i)
    {
        int x1, y1, c1;
        fin >> x1 >> y1 >> c1;
        graph.push_back({x1, y1, c1});
    }
    
    sort(graph.begin(), graph.end(), compare);
    
    for(auto muchie : graph)
    {
        if(dsu.FindFather(muchie.x) != dsu.FindFather(muchie.y))
        {
            dsu.Join(muchie.x, muchie.y);
            cost += muchie.cost;
            nr_muchii++;
            ans.push_back({muchie.x, muchie.y});
        }
    }
    fout << cost << '\n' << nr_muchii << '\n';
    
    for(auto x : ans)
    {
        fout << x.first << ' ' << x.second << '\n';
    }
}