#include <bits/stdc++.h>

using namespace std;

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

struct str {
    int nod,cost;
    bool operator <(const str &aux)const{
        return cost>aux.cost;
    }
};

int n,m;
vector<int>d,t;
vector<vector<pair<int,int>>>a;
vector<bool>fol;
priority_queue<str>pq;


int main() {
    fin>>n>>m;
    a.resize(n+1);
    d.resize(n+1,INT_MAX);
    fol.resize(n+1,false);
    t.resize(n+1,0);
    int x,y,k;
    for(int i=0;i<m;i++){
        fin>>x>>y>>k;
        a[x].push_back({y,k});
        a[y].push_back({x,k});

    }
    d[1]=0;
    pq.push({1,0});
    int costapm=0;
    while(!pq.empty()) {
        int nod=pq.top().nod;
        pq.pop();
        if(fol[nod]) continue;
        fol[nod]=true;
        costapm+=d[nod];
        for(auto f:a[nod]){
            if(!fol[f.first]&&f.second<d[f.first]){
                d[f.first]=f.second;
                t[f.first]=nod;
                pq.push({f.first,d[f.first]});
            }
        }
    }
    fout<<costapm<<'\n';
    for(int i=0;i<n;i++) if(t[i]) fout<<i<<" "<<t[i]<<'\n';

    return 0;
}