#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
int n,m; f>>n>>m;
long long costT=0;
priority_queue<tuple<int,int,int>> pq; //cost,nod,parinte
vector<vector<tuple<int,int>>> graf(n+1); //nod,cost
vector<tuple<int,int>> sol;
vector<bool> vizitat(n+1,0);
for(int i=0;i<m;i++){
    int x,y,c; f>>x>>y>>c;
    graf[x].push_back({y,c});
    graf[y].push_back({x,c});
}
pq.push({0,1,0});
while(pq.size()){
    auto [c,n,p]=pq.top();
    pq.pop();
    c=-c;
    if(vizitat[n])
        continue;
    vizitat[n]=1;
    costT+=c;
    if(p!=0)
        sol.push_back({p,n});
    for(int i=0;i<graf[n].size();i++){
        auto [muchie,cost]=graf[n][i];
        pq.push({-cost,muchie,n});
    }
}
g<<costT<<endl<<sol.size()<<endl;
for(int i=0; i<sol.size(); i++){
    auto [x,y]=sol[i];
    g<<x<<" "<<y<<endl;
}
return 0;
}