#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

long long int t,m,c,u,v,curr,vec,x,y,ok,mask,cost,maxi,b,poz,pozc,n,k,i,j,sp[200005],a[200005],l[200005],r[200005],ll,rr,mij,mini,p,ans,nr,sum,mod=1e9+7;
string s;
//vector<int>g[200005];
queue<int>q;


struct graf
{
    int x,y,cost;
};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vector<graf>g(m);
    vector<vector<int>>adj[n];
    for(i=0; i<m; i++)
    {
        cin>>g[i].x>>g[i].y>>g[i].cost;
        g[i].x--;
        g[i].y--;
        adj[g[i].x].push_back({g[i].y,g[i].cost});
        adj[g[i].y].push_back({g[i].x,g[i].cost});
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
    vector<bool>viz(n,0);
    vector<pair<int, int>> arbore;

    pq.push({0,0});
    auto curr=pq.top();
    int v=0;
    while(!pq.empty())
    {
        auto curr=pq.top();
        pq.pop();
        int u=curr.second;
        int cost=curr.first;
        //cout<<u<<' '<<cost<<endl;

        if(viz[u]==1)
            continue;

        ans+=cost;
        if(!(u==0 && v==0))
            arbore.push_back({u+1,v+1});
        viz[u]=1;
        v=u;

        for(auto v:adj[u])
        {
            if(viz[v[0]]==0)
            pq.push({v[1],v[0]});
        }
    }
    cout<<ans<<endl;
    cout<<arbore.size()<<endl;
    for(const auto &muchie:arbore)
        cout<<muchie.first<<' '<<muchie.second<<endl;
    return 0;
}