#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
#include <stack>
#include <string.h>

using namespace std;
//
//const int NMAX = 1e6;
//
//vector<int> G[NMAX + 1];
//int vis[NMAX+1] = {0};
//
////LABORATOR 1
//void DFS(int x){
//    vis[x]=1;
//    cout<<x<<":";
//    for (auto next: G[x]) {
//        if(vis[next] == 0) {
//            cout<<next<<endl;
//            DFS(next);
//        }
//    }
//
//}
//
//
//void problemaDFS(){
//    ifstream in("dfs.in");
//    ofstream of("dfs.out");
//
//    int N=0, M;
//    in >> N >> M;
//
//    int comp = 0;
//
//    for (int i = 0; i < M; ++i) {
//        int x, y;
//        in >> x >> y;
//        G[x].push_back(y);
//        G[y].push_back(x);
//    }
//
//    for (int i = 1; i <= N; ++i) {
//        if(vis[i] == 0){
//            DFS(i);
//            comp++;
//        }
//    }
//
//    of<<comp;
//}
//
//void problemabBFS(){
//    ifstream in("bfs.in");
//    ofstream of("bfs.out");
//
//    queue<int> q;
//
//    int N,M,S,F;
//
//    in>>N>>M>>S>>F;
//    int viz[N+1];
//    for (int i = 1; i <= N; ++i) {
//        viz[i] = 0;
//    }
//    for (int i = 0; i <M; ++i) {
//        int x,y;
//        in>>x>>y;
//        G[x].push_back(y);
//    }
//
//    q.push(S);
//    viz[S] = 1;
//    while (!q.empty()){
//        int u = q.front();
//        viz[u] = 1;
//        q.pop();
//        for(auto v : G[u]){
//            if(!viz[v]){
//                q.push(v);
//                if(v == F){
//                    cout<<"Gasit";
//
//                }
//            }
//        }
//    }
//}
//
////vector<int> G[NMAX + 1];
//
////vectorul de culori
//int col[NMAX+1]={0};
////daca nu e ok, terminam
//bool ok = true;
//void bfsBipartit(int x){
//    col[x] = 1;
//    //facem o parcurgere BFS si coloram nodurile
//    queue<int> q;
//    q.push(x);
//    while(!q.empty()){
//        x=q.front();
//        q.pop();
//        for(auto next: G[x]){
//            if(!col[next]){
//                col[next] = 3 - col[x];
//                q.push(next);
//            }else{
//                if(col[next] == col[x]){
//                    ok = false;
//                }
//            }
//        }
//    }
//}
//
////folosim o lista de adiacenta pentru BFS, deci complexitatea o sa fie pt parcurgere O(n+m)
////complexitatea finala o sa fie O(n+m) pentru ca ultimul for care itereaza componentele conexe nu afecteaza complexitatea
//void problemaBipartit(){
////    ifstream in("bipartit.in");
//    int n,m;//noduri,muchii;
//    cin>>n>>m;
//
//    //construim lista de adiacenta
//    while(m--){
//        int x,y;
//        cin>>x>>y;
//        G[x].push_back(y);
//        G[y].push_back(x);
//    }
//
//    //rulam pentru fiecare componenta conexa
//    for (int i = 1; i <= n; ++i) {
//        if(!col[i]){
//            bfsBipartit(i);
////            cout<<"chemat "<<i<<endl;
//            if(!ok){
//                cout<<"IMPOSSIBLE";
//                break;
//            }
//        }
//
//    }
//    if(ok)
//        for (int j = 1; j <= n; ++j) {
//            cout<<col[j]<<" ";
//        }
//}
//
//int d[NMAX+1] = {0};
//
//
//stack<int> dfsTopologic(int x){
//    stack<int> s;
//    cout<<"Chem "<<x<<endl;
//    vis[x] = 1;
////    cout<<x<<":";
//    for(auto v : G[x]){
//        cout<<v<<"/"<<vis[v]<<endl;
//        if(!vis[v]){
//            dfsTopologic(v);
//        }
//    }
//    s.push(x);
//    return s;
//}
//
////void problemaTopologicaDFS(){
////    ifstream in("top.in");
////    int n,m;//noduri,muchii;
////    in>>n>>m;
////    cout<<n<<"-"<<m;
////
////    vector<stack<int>> stacks;
////
////    while(m--){
////        int x,y;
////        in>>x>>y;
////        G[x].push_back(y);
////        d[y]++;
////    }
////    cout<<n<<"-"<<m;
////    for (int i = 1; i <= n; ++i)
////        if(!vis[i])
////            stacks.push_back(dfsTopologic(i));
////}
//
//struct muchie{
//    int x,y,c;
//};
//
//muchie a[400001];
//int h[200001],t[200001];
//
//bool comp(muchie &a, muchie &b){
//    return a.c < b.c;
//}
//
//int s = 0;
//void Union(int x, int y){
//    if(h[x] < h[y]){
//        t[x] = y;
//    }else{
//        t[y] = x;
//        if(h[y] == h[x]){
//            h[y]++;
//        }
//    }
//}
//int p;
//int Find(int x){
//    int r=x;
//    while(r != t[r]) {
//        r=t[r];
//    }
//    int y =x;
//    while(x != r){
//        p = t[x];
//        t[x] = r;
//        x=p;
//    }
//    return r;
//}
//stack<int> sc;
//bool printCiclu(int x, int s){
//
//    vis[x] = 1;
//
//    for(auto v : G[x]){
//        if(v==s) return true;
//        if(!vis[v])
//            if(printCiclu(v,s)){
//                sc.push(v);
//                return true;
//            }
//    }
//    return false;
//}
//
////O(n+m) de la BFS
//void problemaTopologica(){
//    ifstream in("top.in");
////citim
//    int n,m;//noduri,muchii;
//    in>>n>>m;
////    cout<<n<<"-"<<m;
//
//    while(m--){
//        int x,y;
//        in>>x>>y;
//        G[x].push_back(y);
//        d[y]++;
//    }
//
//
//    queue<int> c;
//    //punem toate elementele cu gradul intern 0 in coada
//    for (int i = 1; i <= n; ++i)
//        if(d[i] == 0)
//            c.push(i);
//
//    //pastram toate nodurile rezultate intr-un string
//    string str;
//    //parcurgem BFS
//    while(!c.empty()){
//        int u = c.front();
//        c.pop();
//        //adaugam nodul din coada la str
//        str.append(to_string(u)+" ");
//        for(auto v : G[u]){
//            //scadem gradele vecinilor
//            d[v] = d[v] - 1;
//            //daca raman cu gradul intern 0, ii adaugam in coada
//            if(!d[v])
//                c.push(v);
//        }
//    }
//    //verificam daca au ramas noduri pe-afara
//    for (int i = 1; i <= n; ++i)
//        if(d[i] != 0){
//
//            cout<<"IMPOSSIBLE"<<endl;
//            cout<<i<<" ";
//            printCiclu(i,i);
//            while(!sc.empty()){
//                cout<<sc.top()<<" ";
//                sc.pop();
//            }
//            cout<<i<<" ";
//
//            return;
//        }
//    //le afisam daca e totul ok
//    cout<<str;
//}
//
//void fillBFS(int x){
//    queue<int> c;
//    c.push(x);
//    vis[x]=1;
//    while(!c.empty()){
//        int u = c.front();
//        c.pop();
//        for(auto v : G[u]){
//            if(!vis[v]){
//                c.push(v);
//                vis[v]=1;
//            }
//
//        }
//    }
//}
//int mat[10000][10000];
////complexitate O(n*m)
//void problemaFill(){
////    ifstream in("fill.in");
//    int n,m;//noduri,muchii;
////    cout<<"citim n si m"<<endl;
//    cin>>n>>m;
//
//    int index = 1;
////    cout<<"incarcam.."<<endl;
//    for (int i = 1; i <= n; ++i) {
//        for (int j = 1; j <= m; ++j) {
//            char c;
//            cin>>c;
//            if(c=='.'){
//                mat[i][j]=index;
//                //verificam sus
//                if(i-1>0 && mat[i-1][j] > 0){
////                    cout<<index<<"-"<<mat[i-1][j]<<endl;
//                    G[index].push_back(mat[i-1][j]);
//                    G[mat[i-1][j]].push_back(index);
//                }
//
//                //verificam in stanga
//                if(j-1>0 && mat[i][j-1] > 0){
////                    cout<<index<<"-"<<mat[i][j-1]<<endl;
//                    G[index].push_back(mat[i][j-1]);
//                    G[mat[i][j-1]].push_back(index);
//                }
//            }else{
//                //setam ca vizualizat ca sa nu mai numere BFS-ul
//                vis[index]=1;
//                mat[i][j]=0;
//            }
//
//            index++;
//        }
//    }
////    cout<<"Facem BFS"<<endl;
//
//// numaram componentele conexe
//    int camere = 0;
//    for (int i = 1; i <= n*m; ++i) {
//        if(!vis[i]){
//            fillBFS(i);
//            camere++;
//        }
//    }
//    cout<<camere;
//}
//
//
//int imparatii[NMAX] = {0};
//vector<int> Gt[NMAX];
//
//stack<int> sortate;
//void sortTopologicImp(int x){
//    vis[x] = 1;
//    for(auto v : G[x]){
//        if(!vis[v]){
//            sortTopologicImp(v);
//        }
//    }
//    sortate.push(x);
//}
//
//void kosarajuDFS(int x, int imp){
//    vis[x] = 1;
//    imparatii[x] = imp;
//
//    for(auto v : Gt[x]){
//        if(!vis[v])
//            kosarajuDFS(v,imp);
//    }
//}
//
//void problemaImparatie(){
////    ifstream in("imp.in");
//    int n,m;//noduri,muchii;
//    cin>>n>>m;
////    cout<<n<<"-"<<m<<endl;
//
//    while(m--) {
//        int x, y;
//        cin >> x >> y;
//        G[x].push_back(y);
//        //facem transpusa
//        Gt[y].push_back(x);
//    }
//
//    //sortam topologic varfurile(O(n+m))
//    for (int i = 1; i <= n; ++i) {
//        if(!vis[i])
//            sortTopologicImp(i);
//    }
//
//    //resetam vectorul de viz
//    for (int i = 1; i <= n; ++i) {
//        vis[i] = 0;
//    }
//
//    //pornim pe transpusa si numaram componentele conexe, incepand de la nodurile cu gradul cel mai mare
//    int imparatie = 0;
//    while(!sortate.empty()){
//        int u = sortate.top();
//        sortate.pop();
//        if(!vis[u]){
//            imparatie++;
//            kosarajuDFS(u, imparatie);
//        }
//
//    }
//
//
////    cout<<endl;
//    cout<<imparatie<<endl;
//    for (int i = 1; i <= n; ++i) {
//        cout<<imparatii[i]<<" ";
//    }
//}
//
//
//int niv[NMAX] = {0};
//int low[NMAX] = {0};
////int a[NMAX] = {}; //vector de articulatii
//int nrInsule = 0;
//int r;//radacina
//int x;//nr fii radacina
//void dfsInsule(int nod, int p){
//    vis[nod] = 1;
//    niv[nod] = niv[p]+1;
//    low[nod] = niv[nod];
//    for(auto v : G[nod]){
//        if(!vis[v]) {
//            dfsInsule(v, nod);
//            if(nod==r)
//                x++;//crestem nr fiilor radacinii
//            else{
//                low[nod] = min(low[v],niv[nod]);
//                if(low[v] >= niv[nod]) {
////                    a[nod] = 1;
//                    nrInsule++;
//                }
//
//            }
//        }else{
//            low[nod] = min(low[nod],niv[v]);
//        }
//    }
//}
//
////complexitate - DFS - O(n+m)
//void problemaInsule(){
//    ifstream in("ins.in");
//    int n,m;//noduri,muchii;
//
//    in>>n;
//    in>>m;
//    while(n!=0){
//        x=0;
//        nrInsule=0;
//        for (int i = 1; i <= n; ++i) {
//            vis[i]=0;
//            niv[i]=0;
//            low[i]=0;
//            G[i].clear();
//        }
////        cout<<"Citit:"<<n<<"-"<<m<<endl;
////        cout<<"m"<<m<<endl;
//        while(m--) {
////            cout<<"citim";
//            int x, y;
//            in >> x >> y;
////            cout<<x<<y<<endl;
//            G[x].push_back(y);
//            G[y].push_back(x);
//        }
//
//        r = 1;
//        dfsInsule(r,0);
//        if(x>=2) {
////        a[r] = 1;
//            nrInsule++;
//        }
//        cout<<nrInsule<<endl;
//    in>>n;
//    in>>m;
//    }
//
//}
//
////vector<int> control;
//vector<vector<int>> distante_totale;
//
////facem un BFS si tinem mintele distantele de la noduri la radacina
////si adaugam vectorul rezultat intr-un vector
//void genDistantaMinimeBFS(int x, int n){
//    vector<int> distanta_la_x(n+1,-1);
//    queue<int> queue;
//    queue.push(x);
//    distanta_la_x[x]=0;
//
//    while(!queue.empty()) {
//        int u = queue.front();
//        queue.pop();
//        for (auto v: G[u]) {
//            if(distanta_la_x[v] == -1){
//                distanta_la_x[v] = distanta_la_x[u]+1;
//                queue.push(v);
//            }
//        }
//    }
//
//    distante_totale.push_back(distanta_la_x);
//}
//
////complexitate O(n*(n+m))
//void problemaControl(){
//    ifstream in("graf.in");
//    ofstream of("graf.out");
//    int n,m;//noduri,muchii;
//
//    in>>n>>m;
//    while(m--) {
//        int x, y;
//        in >> x >> y;
//        G[x].push_back(y);
//        G[y].push_back(x);
//    }
//
//    int c;
//    //pentru fiecare nod de control generam un vector de distante
//    while(in>>c){
//        genDistantaMinimeBFS(c, n);
//    }
//
//    for (int i = 1; i <= n; ++i) {
//        int minD = n;
//        for(auto dist : distante_totale){
////            cout<<dist[i];
//            minD = min(minD,dist[i]);
//        }
//        of<<minD<<" ";
//    }
//}
//
////void kruskal(){
////    s=0;
////    int n,m;
////    cin>>n>>m;
////    for(int i=1;i<=m;i++){
////        cin>>a[i].x>>a[i].y>>a[i].c;
////    }
////    sort(a+1, a+m+1,comp);
////    int r=0;
////    vector<muchie> sol;
////    for (int i = 1; i <= m; ++i) {
////        int p = Find(a[i].x);
////        int q = Find(a[i].y);
////        if(p != q){
////            s = s+a[i].c;
////            sol.push_back(a[i]);
////            Union(p,q);
////        }
////    }
////}
////
////void prim(){
////    int n,m;
////    priority_queue<int> pq;
////    cin>>n>>m;
////    for (int i = 1; i <= m; ++i) {
////        int x,y,c;
////        cin>>x>>y>>c;
////        G[x].push_back(y);
////        G[y].push_back(x);
////    }
////    for (int i = 1; i <= m; ++i) {
////        d[i] = 1e6;
////    }
////    d[1]=0;
////    pq.push({d[1],1});
////    int s=0;
////
////    while(!pq.empty()){
////        int x = pq.top().second();
////        pq.pop();
////        if(vis[x])
////            continue;
////        vis[x] = 1;
////        s=s+d[x];
////        for(auto next : G[x]){
////            if(!vis[next.first] && d[next.first]) > next.second){
////                d[next.first] = next.second;
////                t[next.first]=x;
////                pq.push({d[next.front], next.first});
////            }
////        }
////    }
////}



const int NMAX = 10e6;
int tata[NMAX + 1], h[NMAX + 1];

struct Muchie {
    int u, v, w;
};

bool comparareMuchii(Muchie a, Muchie b) {
    return a.w < b.w;
}

int Find(int u) {
    if(tata[u] == 0)
        return u;

    tata[u] = Find(tata[u]);
    return tata[u];
}

void Union(int u, int v) {
    int ru, rv;
    ru = Find(u);
    rv = Find(v);
    if (h[ru] > h[rv]) {
        tata[rv] = ru;
    } else {
        tata[ru] = rv;
        if (h[ru] == h[rv]) {
            h[rv]++;
        }
    }
}

void kruskal() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    int n, m, cost_totat = 0, nr_drumuri = 0;
    f >> n >> m;

    vector<Muchie> muchii(m + 1);
    vector<Muchie> sol;

    for (int i = 0; i < m; i++) {
        f >> muchii[i].u >> muchii[i].v >> muchii[i].w;
    }

    sort(muchii.begin(), muchii.end(), comparareMuchii);

    for (int i = 0; i < m; i++) {
        int u = muchii[i].u;
        int v = muchii[i].v;
        int w = muchii[i].w;

        int ru = Find(u);
        int rv = Find(v);

        if (ru != rv) {
            cost_totat = cost_totat + w;
            nr_drumuri++;
            sol.push_back(muchii[i]);
            Union(ru, rv);
        }
    }

    g << cost_totat << endl;
    g << nr_drumuri << endl;

    for(auto varf : sol) {
        g << varf.v << " " << varf.u << endl;
    }

    f.close();
    g.close();
}


int main() {
//  lab 1
//    problemaDFS();
//    problemabBFS();
//tema 1
//    problemaBipartit();
//    problemaTopologica();
//    problemaFill();
//    problemaImparatie();
//    problemaInsule();
//    problemaControl();
//lab 3
    kruskal();

    return 0;
}