#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
//#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int INF = 2e9;

bool sorta(pair<int, int> a, pair<int, int> b)
{
    if(a.first > b.first)
        return 0;
    return 1;
}

vector<int> returnVector(int n, int fillWith){
    vector<int> x;
    x.resize(n + 1);
    std::fill(x.begin(), x.end(), fillWith);
    return x;
}

struct Edge{
    int source, dest, weight;
};

class Graph{

private:
    vector< vector<int> > listaAdiacenta;
    vector<vector<int>  > listaAdiacentaT;
    vector<vector<pair<int, int> > > listaAdiacentaWeighted;
    vector<int> vizitat;
    vector<int> distante;
    vector<pair<int, int> > vizitatT;
    stack < int > Stiva;
    vector <pair<int, pair < int, int> > > edges;
    vector <int> edgeVizited;
    vector< vector<int> > capacity;
    int n;
    int MAXIM = 1 << 30;
public:
    Graph(int n1, int m1) : n(n1){
        this->listaAdiacenta.resize(n1 + 1);
        this->listaAdiacentaT.resize(n1 + 1);
        this->listaAdiacentaWeighted.resize(n1 + 1);
        this->capacity.resize(n1 + 1);
        for( int i = 0; i <= n1; ++i ) {
            this->capacity[i].resize(n1 + 1);
            std::fill(this->capacity[i].begin(), this->capacity[i].end(), 0);
        }
        this->vizitat = returnVector(n1 + 1, 0);
        this->vizitatT.resize(n1 + 1);
        this->distante = returnVector(n1 + 1, this->MAXIM);
        this->edgeVizited = returnVector(m1 + 1, 0);
    };

    Graph(int n1, int m1, bool light): n(n1){
        this->listaAdiacentaWeighted.resize(n1);
        this->vizitat = returnVector(n1 + 1, 0);
    }

    void adaugMuchie(int deLa, int la){
        this->listaAdiacenta[deLa].push_back(la);
    }

    void adaugMuchie(int deLa, int la, int cost){
        this->capacity[deLa][la] = cost;
        this->capacity[la][deLa] = 0;
        this->listaAdiacentaWeighted[deLa].push_back({la, cost});
        this->listaAdiacenta[deLa].push_back(la);
    }

    void adaugMuchie(int deLa, int la, int cost, bool light){
        this->edges.push_back(make_pair(deLa, make_pair(la, cost)));
    }


    void adaugMuchieT(int deLa, int la){
        this->listaAdiacentaT[deLa].push_back(la);
    }

    void dfs(int varf){
        vizitat[varf] = true;
        for (int p: listaAdiacenta[varf]) {
            if(!vizitat[p]){
                dfs(p);
            }
        }
    }

    void dfs1(int varf){
        vizitat[varf] = 1;
        for (int p: listaAdiacenta[varf]) {
            if(!vizitat[p]){
                dfs1(p);
            }
        }
        Stiva.push(varf);
    }

    void dfs2(int varf, int contorComp){
        vizitatT[varf].first = contorComp;
        vizitatT[varf].second = varf;
        for (int p: listaAdiacentaT[varf]) {
            if(!vizitatT[p].first){
                dfs2(p, contorComp);
            }
        }
    }

    void dfsVisited(int varf, vector<int> &visited){
        this->vizitat[varf] = true;
        for (int p: listaAdiacenta[varf]) {
            if(!this->vizitat[p]){
                this->dfsVisited(p, visited);
            }
        }
        visited.push_back(varf);
    }

    int nrComponenteConexe(){

        int contor = 0;
        for(int i = 1;i<=n;++i){
            if(!vizitat[i]){
                ++contor;
                dfs(i);
            }
        }

        return contor;

    }

    void print(){
        for (int i = 1; i <= n; i++)
        {
            // print the current vertex number
            cout << i << " ---> ";

            // print all neighboring vertices of a vertex `i`
            for (int v: listaAdiacenta[i]) {
                cout << v << " ";
            }
            cout << endl;
        }
    }

    void bfs(int startNo){

        int prim, ultim, i;
        queue <int> q;
        q.push(startNo);

        vizitat[startNo] = 1;

        while (!q.empty()){
            int nodAcutal = q.front();
            q.pop();
            for (int p: listaAdiacenta[nodAcutal]) {

                if(vizitat[p] == 0){
                    vizitat[p] = vizitat[nodAcutal] + 1;
                    q.push(p);
                }

            }
        }
    }

    void afisareVizitat(){
        for(int i = 1;i<=n;++i)fout<<vizitat[i] - 1<<" ";
    }

    void componenteTare(){


        for(int i = 1;i<=n;++i){
            if(!vizitat[i]){
                dfs1(i);
            }
        }

        int contorComp = 0;
        while(!Stiva.empty()){

            int varf = Stiva.top();
            Stiva.pop(); /// nu l mai folosim
            if(!vizitatT[varf].first){
                contorComp++;
                dfs2(varf, contorComp);
            }
        }

        fout<<contorComp<<endl;
        int cnt=1;
        //sort(vizitatT.begin() + 1, vizitatT.end(), sorta);


        for(int i=1;i<=n;i++)
        {
            if(vizitatT[i].first > cnt)
            {
                fout<<'\n';
                cnt++;
            }
            if(vizitatT[i].first == cnt)
                fout<<vizitatT[i].second<<' ';
        }


    }

    void sscDfs(int startNode, int n, int &id, stack<int> &stack, vector<int> &onStack, vector<int> &low, vector<int> &ids, vector<vector<int>> &sscComponents){
        stack.push(startNode);
        onStack[startNode] = 1;
        ids[startNode] = low[startNode] = ++id;

        for(int vertex: this->listaAdiacenta[startNode]){
            if(ids[vertex] == 0) this->sscDfs(vertex, n, id, stack, onStack, low, ids, sscComponents);
            if(onStack[vertex]){
                int minim = (low[startNode] < low[vertex] ? low[startNode] : low[vertex]);
                low[startNode] = minim;
            }
        }
        if(ids[startNode] == low[startNode]){
            vector<int> elements;
            while(stack.top()){
                int vertex = stack.top();
                stack.pop();

                onStack[vertex] = 0;
                low[vertex] = ids[startNode];
                elements.push_back(vertex);
                if(vertex == startNode) {
                    break;
                }
            }
            sscComponents.push_back(elements);
        }
    }

    void getSSCComponents(){
        // unvisited is 0
        int id = 0;
        int sscCounter = 0;
        vector<int> ids = returnVector(this->n, 0);
        vector<int> low = returnVector(this->n, 0);
        vector<int> onStack = returnVector(this->n, 0);
        vector<vector<int>> sscComponents;
        stack<int> stack;
        for(int i = 1;i<=n;++i){
            if(ids[i] == 0){
                this->sscDfs(i, this->n, id, stack, onStack, low, ids, sscComponents);
            }
        }
        fout<<sscComponents.size()<<endl;
        for(int i = 0; i < sscComponents.size() ;++i){
            for(int element: sscComponents[i]){
                fout<<element<<" ";
            }
            fout<<"\n";
        }
    }

    void findAndPushSolution(int x, int y, stack < pair < int, int > > &stack1, vector<vector<int>> &bbComponents)
    {
        vector < int > add;
        pair < int, int > top = stack1.top();
        do {
            top = stack1.top();
            add.push_back(top.first);
            add.push_back(top.second);
            stack1.pop();
        }
        while(top.first != x && top.second != y);
        bbComponents.push_back(add);
    }

    void bcDfs(int startNode, int n, int &id, stack < pair < int, int > > &stack1, vector<int> &low, vector<int> &ids, vector<vector<int>> &bbComponents){
        ids[startNode] = low[startNode] = ++id;
        for(auto v : this->listaAdiacenta[startNode]) {
            if(ids[v] == 0) {
                stack1.push({startNode, v});
                this->bcDfs(v, n, id, stack1, low, ids, bbComponents);
                low[startNode] = min(low[startNode], low[v]);
                if(low[v] >= ids[startNode]) {
                    findAndPushSolution(startNode, v, stack1, bbComponents);
                }
            }
            else {
                low[startNode] = min(low[startNode], ids[v]);
            }
        }
    }

    void BCComponents(){
        int id = 0;
        vector<int> ids = returnVector(this->n, 0);
        vector<int> low = returnVector(this->n, 0);
        vector<int> onStack = returnVector(this->n, 0);
        vector<vector<int>> bbComponents;
        stack < pair < int, int > > stack;
        for(int i = 1;i<=n;++i){
            if(ids[i] == 0){
                this->bcDfs(i, this->n, id, stack, low, ids, bbComponents);
            }
        }
        fout << bbComponents.size()<<endl;
        for(auto component : bbComponents) {
           // sort(component.begin(), component.end());
            // component.erase(unique(component.begin(), component.end()), component.end());
            for(auto w : component) {
                fout << w << " ";
            }
            fout<<endl;
        }
    }

    vector<int> topologicalSort(){
        vector<int> topologicalSortList;
        for(int v = 1;v<=n;++v){
            if (!this->vizitat[v]) {
                vector<int> visitedNodesLocal;
                this->dfsVisited(v, visitedNodesLocal);
                for(int visitedNode: visitedNodesLocal){
                    topologicalSortList.insert(topologicalSortList.begin(), visitedNode);
                }
            }
        }
        return topologicalSortList;
    }

    static bool graphExists(vector<int> &a)
    {
        while (true){
            //sort(a.begin(), a.end(), greater<>());
            if (a[0] == 0)
                return true;

            int firstEl = a[0];
            // firstEL is greatest
            a.erase(a.begin() + 0);
            if ( firstEl > a.size() ) return false;

            for (int i = 0; i < firstEl; ++i){
                a[i]--;
                // doesn t have enough grades
                if (a[i] < 0) return false;
            }
        }
    }

    static bool comparare_functie(pair< int, pair <int, int > > x, pair<int, pair <int, int> > y)
    {
        if(x.second.second == y.second.second){
            return make_pair(x.first,x.second.first) < make_pair(y.first,y.second.first);
        }

        return x.second.second < y.second.second;
    }

    pair<long long,vector<pair<int,int> > > Kruskall(){

        std::sort (this->edges.begin(), this->edges.end(), comparare_functie) ;
        vector < pair< int,int > > sol;
        for(int i=1; i <= this->n; i++)

            vizitat[i] = i;


        long long cost=0;

        for(auto it : edges)
        {
            int x = it.first;
            int y = it.second.first;
            int z = it.second.second;

            int tataX = vizitat[x];
            int tataY = vizitat[y];

            if(tataX != tataY)
            {
                cost+=z;
                for(int i = 1;i<=this->n;++i){
                    if(vizitat[i] == tataX)vizitat[i] = tataY;
                }
                sol.push_back(make_pair(y,x));
            }
        }


        return make_pair(cost,sol);

    }

    void bellmanFord(int startNode){

        priority_queue<pair<int,int>> pq;
        pq.push({0,startNode});
        this->distante[startNode] = 0;

        while(!pq.empty()){
            int curentNode = pq.top().second;
            pq.pop();
            this->vizitat[curentNode]++;
            if(this->vizitat[curentNode] >= this->n){
                fout<<"Ciclu negativ!";
                return;
            }
            for(pair<int, int> t: this->listaAdiacentaWeighted[curentNode]){
                if(this->distante[curentNode] + t.second < this->distante[t.first]){
                    this->distante[t.first] = this->distante[curentNode] + t.second;
                    pq.push({-this->distante[t.first],t.first});
                }
            }

        }

        for(int i = 2;i<=this->n;++i){
            fout<<this->distante[i]<<" ";
        }
    }

    int bfsMF(int s, int t, vector<int>& parent) {
        fill(parent.begin(), parent.end(), -1);
        parent[s] = -2;
        queue< pair<int, int> > que;
        que.push(make_pair(s, 1 << 30));

        while ( !que.empty() ) {
            int cur = que.front().first;
            int flow = que.front().second;
            que.pop();

            for (int next : this->listaAdiacenta[cur]) {
                if (parent[next] == -1 && capacity[cur][next] > 0) {
                    parent[next] = cur;
                    int new_flow = min( capacity[cur][next], flow );
                    if (next == t) return new_flow;
                    que.push(make_pair(next, new_flow) );
                }
            }
        }

        return 0;
    }

    int maxFlow(int s, int t){
        int flow = 0;
        vector<int> parent(this->n + 1);
        int new_flow;

        while (new_flow = this->bfsMF(s, t, parent)) {
            flow += new_flow;
            int cur = t;
            while (cur != s) {
                int prev = parent[cur];
                capacity[cur][prev] += new_flow;
                capacity[prev][cur] -= new_flow;
                cur = prev;
            }
        }

        return flow;
    }

    void royFloyd(vector<vector<int>> &mat, int n){

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) {
                fin >> mat[i][j];
                if(!mat[i][j] && i != j) mat[i][j] = INF;
            }

        for(int k = 1; k <= n; k++)
            for(int i= 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    mat[i][j] = min( mat[i][j] , mat[i][k] + mat[k][j] );

    }

    void leveledDfs(int start, int nivel, int &maxim, int &pozMaxim){
        this->vizitat[start] = 1;
        if(nivel > maxim){
            pozMaxim = start;
            maxim = nivel;
        }
        for(int vecin: this->listaAdiacenta[start]){
            if( !this->vizitat[vecin] ){
                this->leveledDfs(vecin, nivel + 1, maxim, pozMaxim);
            }
        }
    }

    void Reset()
    {
        for(int i = 1; i <= n+1; i++)
            this->vizitat[i] = 0;
    }

    void hamiltonianCycle(int x, vector<int> &sol){

        while (!this->listaAdiacentaWeighted[x].empty()) {
            int indiceMuchie = this->listaAdiacentaWeighted[x].back().second;
            int vecin = this->listaAdiacentaWeighted[x].back().first;
            this->listaAdiacentaWeighted[x].pop_back();

            if( !this->vizitat[indiceMuchie] ){
                this->vizitat[indiceMuchie] = 1;
                hamiltonianCycle(vecin, sol);
            }
        }
        sol.push_back(x);
    }

    vector<int> solveHamilton(){
        vector<int> sol;
        for(int i = 1 ; i <= this->n ; i++) {
            if (this->listaAdiacentaWeighted[i].size() % 2 == 1)
            {
                vector<int> ret;
                ret.push_back(-1);
                return ret;
            }
        }
        this->hamiltonianCycle(1, sol);
        return sol;

    }

    int getMinimumSumHamiltionianGraph(){
        // returns - 1 if no hamiltionian cycle exists;
        vector < vector < int > > dp(18, vector <int> ((1 << 18), INF));

        dp[0][1] = 0;
        for (int mask = 0; mask < 1 << n; mask++) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    for (auto it : this->listaAdiacentaWeighted[i]) {
                        if (mask & (1 << it.first)) {
                            dp[i][mask] = min(dp[i][mask], dp[it.first][mask ^ (1 << i)] + it.second);
                        }
                    }
                }
            }
        }
        int ans = INF;
        for (auto it : this->listaAdiacentaWeighted[0]) {
            ans = min(ans, dp[it.first][(1 << n) - 1] + it.second);
        }
        if (ans == INF) return -1;
        return ans;
    }



};


int main()
{
    int n, m;
    fin>>n>>m;
    Graph g(n, m, true);
    for(int i = 1;i<=m;++i){
        int a, b, c;
        fin>>a>>b>>c;
        g.adaugMuchie(a, b, c, true);
        g.adaugMuchie(b, a, c, true);

    }
    pair<long long,vector<pair<int,int> > > solution = g.Kruskall();
    fout<<solution.first<<endl;
    fout<<n-1<<endl;

    for(auto it:solution.second)
        fout<<it.first<<' '<<it.second<<"\n";
    return 0;
}