#include <iostream>
#include <cstdio>
#include <bitset>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
set <pair<int,pair<int,int>>> p;
vector <pair<int,int>> sol;
vector <pair<int,int>> g[200002];
int suma, n, m;
bitset <200002> viz;
int a,b,c;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d", &n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("\n%d %d %d", &a,&b,&c);
        g[a].push_back({b,c});
    }
    for(auto i : g[1])
        p.insert({i.second,{1,i.first}});
    viz[1]=1;
    while(sol.size()!=n-1)
    {
        while(viz[p.begin()->second.second])
            p.erase(p.begin());
        sol.push_back({p.begin()->second.first,p.begin()->second.second});
        suma+=p.begin()->first;
        viz[p.begin()->second.second]=1;
        int nod=p.begin()->second.second;
        p.erase(p.begin());
        for(auto i:g[nod])
            p.insert({i.second,{nod,i.first}});
    }
    cout<<suma<<"\n"<<sol.size()<<"\n";
    for(pair<int,int> i: sol)
    {
        cout<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}