#include <bits/stdc++.h>

using namespace std;

const int vmax = 105;

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

unsigned cnt = 0;
queue <int> q;
vector<int> ssol[vmax];
int nivel[vmax];
int nivelMin[vmax];
stack<pair<int, int>> stt;
bool visT[vmax] = {false};
int ctc[vmax] = {0};
vector<int> adjT[vmax];
stack<int> st;
unsigned cnnt = 0;

class Edge{
public:
    int i, j, cost;
    Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}

     friend bool operator<(const Edge& e1, const Edge& e2)
    {
        return e1.cost < e2.cost;
    }
};

class RepRang{
public:
    int rep;
    int rang;
};


bool isThere(int el, vector<int> v){
    for(auto element : v)
        if (element == el)
            return true;
    return false;
}
class Graph{
public:
    int noduri, muchii;
    vector<int> adj[vmax];
    bool vis[vmax];
    Graph(int _noduri, int _muchii): noduri(_noduri), muchii(_muchii){
        //q = queue<int>();
    }

    virtual void build() = 0;
    virtual void bfs(int source) = 0;
    virtual void dfs(int node) = 0;
    virtual void sol() = 0;
    virtual long long getCconexe() = 0;
    virtual void sortareTopologica() = 0;
    virtual void dfsTopologic(int) = 0;
    virtual void dfsBCC(int) = 0;
    virtual void Transpune() = 0;
    virtual void PlusMinus() = 0;
    virtual void Kosaraju() = 0;
};

class OrientedGraph : public Graph{
     int dist[vmax];
public:
    OrientedGraph(int _noduri, int _muchii): Graph(_noduri, _muchii){
            for(int i = 1; i <= noduri; ++i)
                {
                    dist[i] = -1;
                    vis[i] = false;
                }
    }

    virtual void build() override{
        for(int i = 0; i < muchii; ++i){
            int x, y;
            in >> x >> y;
            adj[x].push_back(y);
            }
        }
    void bfs(int source) override{
        q.push(source);
        dist[source] = 0;
        while(!q.empty())
        {
            int crt = q.front();
            q.pop();
            for(unsigned i = 0; i < adj[crt].size(); ++i)
                {
                    if(dist[adj[crt][i]] == -1)
                        {
                            dist[adj[crt][i]] = 1 + dist[crt];
                            q.push(adj[crt][i]);
                        }
                }
        }
    }

    virtual long long getCconexe() override{}

    virtual void dfsTopologic(int node) override{
        vis[node] = true;
        for(unsigned i = 0; i < adj[node].size(); ++i)
            if(!(vis[adj[node][i]]))
                dfsTopologic(adj[node][i]);
        st.push(node);
    }



    virtual void sortareTopologica() override{
        for(int i = 1; i <= noduri; ++i)
            if(!(vis[i]))
                dfsTopologic(i);
    }


    virtual void sol()  override{
        this->sortareTopologica();
        while(st.size()){
            out << st.top() << ' ';
            st.pop();
        }
    }

    virtual void dfsBCC(int nod) override {}


    virtual void dfs(int node) override{
        vis[node] = true;
            for(unsigned i = 0; i < adj[node].size(); ++i)
                if(!(vis[adj[node][i]]))
                    dfs(adj[node][i]);
    }
    virtual void Transpune(){
        for(int i = 1; i <= noduri; ++i)
            for(auto vecin : adj[i])
                adjT[vecin].push_back(i);
    }

    virtual void PlusMinus() override{
        int nrc = 0;
        this->Transpune();
        for(int i = 1; i <= noduri; ++i)
        {
            for(int i = 1; i <= noduri; ++i)
                if(ctc[i] == 0){
                    ++nrc;
                    for(int j = 1; j <= noduri; ++j)
                        vis[j] = visT[j] = false;
                    dfs(i);
                    dfT(i);
                    for(int j = 1; j <= noduri; ++j)
                        if(vis[j] && visT[j])
                            ctc[j] = nrc;
                }
        }

        out << nrc << '\n';
        for(int i = 1; i <= nrc; ++i)
        {
            for(int j = 1; j <= noduri; ++j)
                if(ctc[j] == i)
                    out << j << ' ';
            out << '\n';
        }
    }

    virtual void dfT(int node){
        ssol[cnnt].push_back(node);
        visT[node] = true;
        for(auto vecin: adjT[node])
            if(visT[vecin] == false)
            {
                dfT(vecin);
            }
    }

    virtual void Kosaraju() override{
        this->Transpune();
        this->sortareTopologica();

        while(st.size())
        {   int k = 0;
            while(st.size() && visT[st.top()] == true)
                st.pop();
            if(st.size())
                k = 1;
            if(st.size())
            {
                int crt = st.top();
                dfT(crt);
            }
            if(k == 1)
                ++cnnt;
            if(st.size())
                st.pop();
        }
        out << cnnt << '\n';
        for(int i = 0; i < cnnt; ++i)
            {
            for(auto el: ssol[i])
                out << el << ' ';
            out << '\n';
            }
    }


};

class UnorientedGraph : public Graph{
public:
    vector<Edge> edges;
    RepRang reps[vmax];
    UnorientedGraph(int _noduri, int _muchii) : Graph(_noduri, _muchii){}
    virtual void build() override{
        for(int i = 0; i < muchii; ++i)
        {
            int x, y, cost;
            in >> x >> y >> cost;
            Edge temp(x, y, cost);
            edges.push_back(temp);
        }

    }

    int find_rep(int node){
        if(reps[node].rep == node)
            return node;
        reps[node].rep = find_rep(reps[node].rep);
        return reps[node].rep;  }

    void Union(int node1, int node2){
        int rep1 = find_rep(node1);
        int rep2 = find_rep(node2);

        if(reps[rep1].rang > reps[rep2].rang)
            reps[rep2].rep = rep1;
        else
            if(reps[rep1].rang < reps[rep2].rang)
                reps[rep1].rep = rep2;
            else
                {
                    reps[rep2].rep = rep1;
                    ++reps[rep1].rang;
                }
    }

    void Kruskal(){
        vector<pair<int, int>> ssol;
        unsigned total = 0;
        sort(edges.begin(), edges.end());
        for(int i = 1; i <= noduri; ++i)
        {
            reps[i].rep = i;
            reps[i].rang = 0;
        }

        int cnt = 0;
        int i = 0;
        for(;i < edges.size() && cnt <= muchii - 1; ++i){
            Edge temp_edge = edges[i];
            if(find_rep(edges[i].i) != find_rep(edges[i].j))
            {
                ++cnt;
                ssol.push_back(make_pair(temp_edge.i, temp_edge.j));
                Union(temp_edge.i, temp_edge.j);
                total += temp_edge.cost;
            }
        }
        out << total << '\n';
        out << cnt << '\n';
        for(auto pr: ssol){
            out << pr.first << ' ' << pr.second << '\n';
        }
    }
    virtual void dfs(int node) override{
        vis[node] = true;
        for(unsigned i = 0; i < adj[node].size(); ++i)
            if(!(vis[adj[node][i]]))
                dfs(adj[node][i]);
    }

    void bfs(int source) override{
    }

    virtual long long getCconexe() override{
        long long cnt = 0;
        for(int i = 1; i <= noduri; ++i)
            if(!(vis[i]))
            {
                ++cnt;
                dfs(i);
            }
        return cnt;
    }
    virtual void dfsTopologic(int node){}
    virtual void sortareTopologica() override{}

    virtual void dfsBCC(int nod) override{
    vis[nod] = true;
    nivelMin[nod] = nivel[nod];
    unsigned copii = 0;
    for(auto vecin: adj[nod]){
        if(vis[vecin] == false)
        {
            nivel[vecin] = nivel[nod] + 1;
            stt.push(make_pair(nod, vecin));
            dfsBCC(vecin);
            if(nivelMin[vecin] >= nivel[nod]){

                ssol[cnt].push_back(nod);
                while(!(stt.top().first == nod && stt.top().second == vecin))
                      {
                          //out << stt.top().second << ' ';
                          ssol[cnt].push_back(stt.top().second);
                          stt.pop();
                      }
                ssol[cnt].push_back(vecin);
                stt.pop();
                ++cnt;
            }
                nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin]);

        }
        else if (nivel[nod] - nivel[vecin] >= 2)
            nivelMin[nod] = min(nivelMin[nod], nivel[vecin]);

    }
}
    virtual void sol() override{
            this->dfsBCC(1);
        }
    virtual void PlusMinus() override{

    }

    virtual void Kosaraju() override{
    }
    virtual void Transpune() override{
    }
};

int main()
{
    int N, M, S;
    in >> N >> M;
    UnorientedGraph g(N, M);
    g.build();
    g.Kruskal();
    return 0;

}