#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int MAXN=400010;
const int INF=2e9;

int n,m,cost[MAXN],visit[MAXN],parinte[MAXN];
vector <pair <int,int>>g[MAXN];
priority_queue <pair <int,int>, vector <pair <int,int>>, greater <pair<int,int>>> pq;

int main()
{
    fin >>n>>m;
    for (int i=1;i<=m;++i){
        int x,y,cost;
        fin >>x>>y>>cost;
        g[x].push_back ({cost,y});
        g[y].push_back ({cost,x});
    }

    for (int i=1;i<=n;++i)
        cost[i]=INF;
    cost[1]=0;
    parinte[1]=-1;
    pq.push ({0,1});

    while (pq.empty ()==false){

        while (pq.empty ()==false and visit[pq.top ().second]==1)
            pq.pop ();
        if (pq.empty ()==true)
            break;

        int nod=pq.top().second;
        visit[nod]=1;

        for (int i=0;i<g[nod].size ();++i){
            int nodcrt=g[nod][i].second,costcrt=g[nod][i].first;

            if (cost[nodcrt]>costcrt and visit[nodcrt]==0){
                cost[nodcrt]=costcrt;
                pq.push ({costcrt,nodcrt});
                parinte[nodcrt]=nod;
            }
        }

    }


    long long sum=0;
    for (int i=1;i<=n;++i){
        if (parinte[i]!=-1)
            sum+=cost[i];
    }

    fout <<sum<<'\n';
    fout <<n-1<<'\n';
    for (int i=1;i<=n;++i){
        if (parinte[i]!=-1){
            fout <<i<<' '<<parinte[i]<<'\n';
        }
    }
    fin.close ();
    fout.close ();
    return 0;
}