using namespace std;

#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<numeric>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<deque>

const int INFI=(1LL<<29)-100;
const long long INFL=(1LL<<62);
const double eps=1e-15;
const long double pi=acos(-1.0);
const int MAXN=200010;

vector<pair<int,int> > v[MAXN];
int cost[MAXN],parent[MAXN];
bool chosen[MAXN];

struct cmp{
    bool operator()(const pair<int,int>& p1,const pair<int,int>& p2){
        return p1.second>p2.second;
    }
};

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){
        int x,y,cs;
        scanf("%d%d%d",&x,&y,&cs);
        v[x].push_back(make_pair(y,cs));
        v[y].push_back(make_pair(x,cs));
    }

    priority_queue<pair<int,int>, vector<pair<int,int> >, cmp> pq;

    for(int i=2;i<=n;i++){
        cost[i]=INFI;
    }
    cost[1]=0;
    pq.push(make_pair(1,0));

    while(!pq.empty()){
        int i=pq.top().first;
        pq.pop();

        if(chosen[i]){
            continue;
        }

        for(unsigned j=0;j<v[i].size();j++){
            int u=v[i][j].first;
            int cs=v[i][j].second;
            if(!chosen[u] && cs<cost[u]){
                cost[u]=cs;
                parent[u]=i;
                pq.push(make_pair(u,cs));
            }
        }
        chosen[i]=1;
    }

    int sum=0;
    for(int i=2;i<=n;i++){
        sum+=cost[i];
    }
    printf("%d\n%d\n",sum,n-1);

    for(int i=2;i<=n;i++){
        printf("%d %d\n",i,parent[i]);
    }

    return 0;
}