#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n,m,nodes,cost;
set<pll> muchii[200006];
set<pair<int,pair<int,int>>> mc;
vector<pll> sol;
bool use[200006];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        ll x,y,c;
        fin>>x>>y>>c;
        muchii[x].insert({c,y});
        muchii[y].insert({c,x});
    }
    use[1]=1;
    nodes=1;
    for(auto i:muchii[1])
    {
        int cst=i.first;
        int nod=i.second;
        int nod2=1;
        mc.insert({cst,{nod,nod2}});
    }
    while(nodes<n)
    {
        while(true)
        {
            auto it=mc.begin();
            if(use[(*it).second.first]==0)
            {
                cost+=(*it).first;
                sol.push_back({(*it).second.first,(*it).second.second});
                nodes++;
                int nod=(*it).second.first;
                use[nod]=1;
                for(auto i:muchii[nod])
                {
                    int cst=i.first;
                    int nd=i.second;
                    int nd2=nod;
                    mc.insert({cst,{nd,nd2}});
                }
                mc.erase(it);
                break;
            }
            mc.erase(it);
        }
    }
    fout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto i:sol)
        fout<<i.first<<" "<<i.second<<'\n';
    return 0;
}