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

    use[1]=1;
    for(auto i:v[1])
        q.push({i.first,i.second,1});//muchii

    ans.push_back({1,0});
    sum=0;
    nr=k-1;
    while(nr!=0)
    {
        sum+=q.top().first;
        ans.push_back({q.top().second,q.top().lst});

        x=q.top().second;
        q.pop();
        use[x]=1;
        --nr;

        for(auto i:v[x])
            if(use[i.second]==0)
                q.push({i.first, i.second, x});

        while(q.empty()==false && use[q.top().second]==1)
            q.pop();
    }

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