prim

#include <bits/stdc++.h>
#define MOD 1000000007
#define NMAX 200005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

long long fact[NMAX];

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

vector<pair<int,int> > G[NMAX];
vector<pair<int,int> > sol;
bool inSolution[NMAX];

int main() {
    int n,m,i,x,y,c,cost=0;

    fin>>n>>m;

    for(i=1;i<=m;++i) {
        fin>>x>>y>>c;

        G[x].pb({c,y});
        G[y].pb({c,x});
    }

    priority_queue<pair<pair<int,int>, int>, vector<pair<pair<int,int>, int> >, greater<pair<pair<int,int>, int > > > pq;
    inSolution[1] = 1;
    for(i=0;i<G[1].size();++i) pq.push({G[1][i], 1});

    while((int)sol.size() < n-1) {
        pair<pair<int,int>, int> muchie = pq.top();
        pq.pop();

        int x = muchie.second, y = muchie.first.second;
        if(!inSolution[y]) {
            inSolution[y] = 1;
            cost+=muchie.first.first;

            for(i=0;i<G[y].size();++i) pq.push({G[y][i], y});

            sol.push_back({x, y});
        }
    }

    fout << cost << '\n' << sol.size() << '\n';
    for(auto it:sol)
        fout << it.first << ' ' << it.second << '\n';

    return 0;
}