#include <bits/stdc++.h>
#define INF numeric_limits<int>::max()
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector< vector< pair<int,int> > > a;
vector<bool> use;
vector<int> d,t;
priority_queue< pair<int,int> > q;
void prim(int st)
{
    d[st]=-INF;
    t[st]=0;
    q.push({0,st});
    use[st]=true;
    while(!q.empty())
    {
        pair<int,int> p=q.top();q.pop();
        int x=p.second;
        for(auto i: a[x])
        if(d[i.first] > i.second)
        {
            d[i.first]=i.second;
            t[i.first]=x;
            q.push({-d[i.first],i.first});
        }
    }

}
int main()
{
    int n,m,x,y,z;
    in>>n>>m;
    a=vector< vector< pair<int,int> > >(n+1);
    d=vector<int>(n+1,INF);
    t=vector<int>(n+1);
    use=vector<bool>(n+1);
    for(;m;m--)
    {
        in>>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    prim(1);
    int cost=0;
    for(int i=2;i<=n;i++)cost+=d[i];
    out<<cost<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)out<<i<<' '<<t[i]<<'\n';
    return 0;
}