#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
typedef long long ll;
const ll Nmax=2e5+5, inf=1e9+5;
using pii=pair<int, int>;

int n, m;
vector<pii> ad[Nmax];
bool vis[Nmax];
multiset <pair<int, pii>> st;
vector<pii> vsol;
int main()
{
    fin>>n>>m;
    int a, b, val;
    for (int i=0; i<m; i++){
        fin>>a>>b>>val;
        ad[a].pb({val, b});
        ad[b].pb({val, a});
    }
    int sol=0;
    st.insert({0, {1, 1}});
    while (!st.empty()){
        auto crt=*st.begin();
        st.erase(st.begin());
        if (!vis[crt.se.se]){
            vsol.pb(crt.se);
            vis[crt.se.se]=1;
            sol+=crt.fi;
            for (auto it:ad[crt.se.se])
                st.insert({it.fi, {crt.se.se, it.se}});
        }
    }
    fout<<sol<<'\n';
    fout<<vsol.size()-1<<'\n';
    for (int i=1; i<vsol.size(); i++)
        fout<<vsol[i].fi<<' '<<vsol[i].se<<'\n';

    return 0;
}