#include <iostream>
#include <vector>
#include <fstream>
#include <set>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie{
    int nod1,nod2;
};
int main()
{

    int n,m,i;
    in>>n>>m;
    int inf=1<<24;
    vector <vector<pair<int,int>>> G(n+1);
    set<pair<int,pair<int,int>>> S;
    vector<int> viz(n+1,0);

    for(i=1;i<=m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        G[x].push_back({c,y});
        G[y].push_back({c,x});
    }
    vector <int> Minim(n+1,inf);
    int k=0;
    viz[1]=1;
    for(auto i: G[1])
    {
        S.insert({i.first,{1,i.second}});
    }
    long long cost=0;
    vector<pair<int,int>>sol;
    while(k!=n-1)
    {
        pair<int,pair<int,int>> p=(*S.begin());
        S.erase(S.begin());
        if(viz[p.second.second]==0)
        {
            viz[p.second.second]=1;
            sol.push_back(p.second);
            cost=cost+p.first;
            k++;
            for(auto i:G[p.second.second])
            {
                if(viz[i.second]==0)
                    S.insert({i.first,{p.second.second,i.second}});
            }
        }

    }


    out<<cost<<"\n";
    out<<n-1<<"\n";
    for(auto i: sol)
    {
        out<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}