#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define cs(x) 1000-x


vector<pair<int,int> > muchie[400001];
int viz[400001];
vector<pair<int,pair<int,int> > >h;
vector<pair<int,int> > sol;

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    int n,m,x,y,cost;

    f>>n>>m;

    for(int i=0;i<m;i++){
        f>>x>>y>>cost;
        muchie[x].push_back(make_pair(y,cost));
        muchie[y].push_back(make_pair(x,cost));
    }
    viz[1]=1;

    for(int i=0;i<muchie[1].size();++i){
        h.push_back(make_pair(cs(muchie[1][i].second),make_pair(1,muchie[1][i].first)));
    }

    make_heap(h.begin(),h.end());

    int cT=0;

    int j;
    for(j=0;j<n-1;){
        int c;
        pair<int,pair<int,int> > th;
        th=h.front();
        pop_heap (h.begin(),h.end());
        h.pop_back();

        c=cs(th.first);
        cout<<c<<" ";
        if(viz[th.second.second]==0){

            viz[th.second.second]=1;
            sol.push_back(make_pair(th.second.first,th.second.second));
            cT+=c;

            for(int i=0;i<muchie[th.second.second].size();++i){
                if(viz[muchie[th.second.second][i].first]==0){
                    h.push_back(make_pair(cs(muchie[th.second.second][i].second),make_pair(th.second.second,muchie[th.second.second][i].first)));
                    push_heap(h.begin(),h.end());
                }
            }
            j++;
        }

    }

    g<<cT<<'\n'<<n-1<<'\n';
    for(int i=0;i<sol.size();i++){
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
    }


    return 0;
}