#include <bits/stdc++.h>
#define NMAX 200200
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct poz{
    int first, second, third;
    bool operator<(poz b)const{
        if(third!=b.third)
            return third>b.third;
        if(first!=b.first)
            return first<b.first;
        return second<b.second;
    }
};
priority_queue<poz>q;
deque<pair<int,int>>ans;
vector<pair<int,int>>v[NMAX];
int n, m, x, y, c, t, use[NMAX];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({c,y});
        v[y].push_back({c,x});
    }

    q.push({0,1,0});
    while(!q.empty())
    {
        x=q.top().second;
        use[x]=1;
        ans.push_back({q.top().first, q.top().second});
        t=t+q.top().third;
        q.pop();

        for(auto i:v[x])
            if(use[i.second]==0)
                q.push({x, i.second, i.first});
        while(!q.empty() && use[q.top().second]==1)
            q.pop();
    }

    ans.pop_front();
    fout<<t<<'\n'<<ans.size()<<'\n';
    for(auto i:ans)
        fout<<i.first<<" "<<i.second<<'\n';
    return 0;
}