#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m;
int x,y,c;
vector<int> D;
struct muchie{
    int nod;
    int cost;
};
vector<vector<muchie>> A;
struct cmp{
    bool operator() (const int &a,const int &b)
    {
        return D[a]>D[b];
    }
};
int total;
vector<bool> fr;
vector<pair<int,int>> ans;
int main()
{
    cin>>n>>m;
    A.resize(n+1);
    D.resize(n+1);
    fr.resize(n+1);
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>c;
        A[x].push_back({y,c});
        A[y].push_back({x,c});
    }
    D[1]=0;
    priority_queue<int,vector<int>,cmp> Q;
    for(int i=2;i<=n;i++)
        D[i]=0x3f3f3f3f;
    for(int i=0;i<A[1].size();i++)
    {
        int vecin=A[1][i].nod;
        int cost=A[1][i].cost;
        D[vecin]=min(D[vecin],cost);
    }
    fr[1]=1;
    for(int i=2;i<=n;i++)
       Q.push(i);
    while(!Q.empty())
    {
        int cap=Q.top();
        //cout<<D[cap]<<'\n';
       // for(int i=1;i<=n;i++)
          // if(!fr[i])
              //cout<<D[i]<<" ";
       // cout<<'\n';
        total=total+D[cap];
        fr[cap]=1;
        bool ok=1;
        for(int i=0;i<A[cap].size();i++)
        {
         int vecin=A[cap][i].nod;
         int cost=A[cap][i].cost;
         if(ok)
         if(cost==D[cap] && fr[vecin])
           {
               ans.push_back({cap,vecin});
               ok=0;
           }
          if(!fr[vecin])
         D[vecin]=min(D[vecin],cost);
        }
        D[cap]=0;
        Q.pop();
    }
    cout<<total<<'\n';
    cout<<n-1<<'\n';
    for(int i=0;i<ans.size();i++)
       cout<<ans[i].first<<" "<<ans[i].second<<'\n';
    return 0;
}