#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");


struct Weigthed_Edge{

    int u,v,weight;

    Weigthed_Edge(int a, int b, int c):u(a),v(b),weight(c){}
    ~Weigthed_Edge() = default;

    bool operator<(const Weigthed_Edge &b) const
    {
        return this->weight<b.weight;
    }
};

class Graph{
private:
    int n;
    vector < vector<int> > la;

    vector<vector<int>> componente_biconexe;
    vector<vector<int>> componente_tconexe;
    vector<int> lowest, level, father, degrees;
    vector<bool> onstack;
    stack<int> S;
    stack<pair<int,int>> edges_biconexe;
    int index;

    void dfs(int nod_crt, vector<bool> &viz);
    void dfs_biconexe(int nod_crt);
    void dfs_tarjan(int nod_crt);
    void add_cmp_biconexa(int x, int y);
    bool consume(int nr, int poz);
    bool static max_flow_bfs(int source, int terminal, vector<vector<int>>& flow, vector<vector<int>>& capacity, vector<vector<int>>& la, vector<int>& pred, vector<bool>& viz);


public:
    Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1), componente_biconexe(0), componente_tconexe(0), lowest(0), level(0), father(0), onstack(0), index(0), degrees(0){}

    ~Graph() = default;

    void add_edge(int from, int to){
        la[from].push_back(to);
    }
    void bfs_print_dist(int start=1); // Starting from node 1 by default
    int nr_conexe_dfs();
    void print_sortare_topologica(ostream &out);
    void print_comp_biconexe_udg(ostream &out);
    void print_comp_tconexe_dg(ostream &out);
    bool Havel_Hakimi(vector<int> &grade_noduri);

    void static print_dist_BellmanFord(ostream &out, int start, vector<Weigthed_Edge> &edges, int nn);
    void static print_dist_SPFA(ostream &out, int start, vector<vector<pair<int,int>>> &DWG, int nn);
    void static print_APM_Kruskal(ostream &out, vector<Weigthed_Edge> &edges, int nn);
    void static solve_disjoint(istream &in, ostream &out);
    void static update_disjoint(int x, vector<int> &father);
    vector<int> static Dijkstra(vector<vector<pair<int,int>>> &DWG, int start_node, int nn, const int inf);

    int TD();
    void static royFloydWarshall(vector<vector<int>>& distMat, vector<vector<int>>& pred, int inf);
    int static max_flow(int n, int source, int terminal, vector<Weigthed_Edge> &DWG);

    int static min_hamiltonian_cycle(int n, vector<Weigthed_Edge>& DWG, int inf);
    vector<int> static find_eulerian_cycle(int n, vector<pair<int,int>> edges); /// if the returned vector is empty then there is no eulerian cycle

};


void Graph::bfs_print_dist(int start)
{
    vector<int> dist(n+1,0);
    queue<int> q;
    int nod_crt;

    q.push(start);
    dist[start]=1;

    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin: la[nod_crt])
        {
            if(dist[nod_vecin] == 0)
            {
                dist[nod_vecin] = dist[nod_crt] + 1;
                q.push(nod_vecin);
            }
        }
    }

    for(int i=1;i<=n;++i)
        g<<dist[i]-1<<' ';
}

int Graph::nr_conexe_dfs()
{
    vector<bool> viz(n+1, false);
    int nr_c=0;
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            ++nr_c;
            dfs(i, viz);
        }
    }

    return nr_c;
}


void Graph::print_sortare_topologica(ostream &out)
{
    queue<int> zero_nodes;
    degrees.resize(n+1,0);
    int nod_curent, i;
    for(i=1;i<=n;++i)
    {
        for(auto nod_vecin: la[i])
            ++degrees[nod_vecin];
    }
    for(i=1; i<=n;++i)
        if(degrees[i] == 0)
            zero_nodes.push(i);
    if(zero_nodes.empty())
    {
        cout<<"Cyclic Graph. Can't sort.";
        return;
    }
    while(!zero_nodes.empty())
    {
        nod_curent = zero_nodes.front();
        zero_nodes.pop();
        out<<nod_curent<<' ';

        for(auto nod_vecin: la[nod_curent])
        {
            --degrees[nod_vecin];
            if(degrees[nod_vecin] == 0)
                zero_nodes.push(nod_vecin);
        }
    }
    degrees.clear();
}

void Graph::dfs(int nod_crt, vector<bool> &viz)
{

    for(auto nod_vecin: la[nod_crt])
    {
        if(!viz[nod_vecin])
        {
            viz[nod_vecin] = true;
            dfs(nod_vecin, viz);
        }
    }

}


void Graph::add_cmp_biconexa(int x, int y)
{
    int a,b;
    vector<int> componenta_biconexa;
    do
    {
        a=edges_biconexe.top().first;
        b=edges_biconexe.top().second;

        edges_biconexe.pop();

        componenta_biconexa.push_back(a);
        componenta_biconexa.push_back(b);

    }while((a!=x || b!=y) && !edges_biconexe.empty());

    sort(componenta_biconexa.begin(), componenta_biconexa.end() );
    componente_biconexe.push_back(componenta_biconexa);
}

void Graph::dfs_biconexe(int nod_crt)
{
    level[nod_crt] = level[father[nod_crt]] + 1;
    lowest[nod_crt] = level[nod_crt];

    for(auto nod_vecin: la[nod_crt])
    {
        if(level[nod_vecin] == 0)
        {
            father[nod_vecin] = nod_crt;
            edges_biconexe.push(make_pair(nod_crt, nod_vecin));

            dfs_biconexe(nod_vecin);

            if(lowest[nod_vecin] >= level[nod_crt])
                add_cmp_biconexa(nod_crt, nod_vecin);

            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(nod_vecin!= father[nod_crt])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);;
    }


}

void Graph::print_comp_biconexe_udg(ostream &out)
{
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);
    father.resize(n+1, 0);

    dfs_biconexe(1);

    out<<componente_biconexe.size()<<'\n';
    for(auto componenta:componente_biconexe)
    {
        out<<componenta[0];
        for(int i=1;i<componenta.size();++i)
            if(componenta[i]!=componenta[i-1])
                out<<' '<<componenta[i];
        out<<'\n';
    }

    lowest.clear();
    level.clear();
    father.clear();
}



void Graph::dfs_tarjan(int nod_crt)
{
    ++index;
    level[nod_crt] = index;
    lowest[nod_crt] = index;
    S.push(nod_crt);
    onstack[nod_crt] = true;

    for(auto nod_vecin : la[nod_crt])
    {
        if(level[nod_vecin]==0)
        {
            dfs_tarjan(nod_vecin);
            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(onstack[nod_vecin])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);
    }

    if(level[nod_crt] == lowest[nod_crt])
    {
        vector<int> comp_tconexa;
        int st;
        do
        {
            st = S.top();
            S.pop();
            onstack[st]=false;
            comp_tconexa.push_back(st);
        }while(st!=nod_crt);

        componente_tconexe.push_back(comp_tconexa);
    }

}

void Graph::print_comp_tconexe_dg(ostream &out)
{
    onstack.resize(n+1, false);
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);

    for(int i=1;i<=n;++i)
    {
        if(level[i] == 0)
        {
            dfs_tarjan(i);
        }
    }
    out<<componente_tconexe.size()<<'\n';
    for(auto comp: componente_tconexe)
    {
        for(auto nod:comp)
            out<<nod<<' ';
        out<<'\n';
    }
    onstack.clear();
    lowest.clear();
    level.clear();
}


bool Graph::consume(int nr, int poz)
{
    if(nr == 0)
        return true;
    if(poz == 0)
        return false;

    if(nr>degrees[poz])
    {
        bool ok = consume(nr-degrees[poz], poz-1);
        degrees[poz-1]+=degrees[poz];
        degrees[poz]=0;
        return ok;
    }

    degrees[poz-1]+=nr;
    degrees[poz]  -=nr;

    return true;
}

bool Graph::Havel_Hakimi(vector<int>& grade_noduri)
{
    int sum=0, max_grade = 0;
    degrees.resize(n, 0);
    for(auto x: grade_noduri)
    {
        if(x>=n)
        {
            degrees.clear();
            return false;
        }

        ++degrees[x];
        sum+=x;

        if(x>max_grade)
            max_grade = x;
    }
    if( sum & 1)
    {
        degrees.clear();
        return false;
    }
    if(max_grade <=1 )
    {
        degrees.clear();
        return true;
    }

    for(int i=max_grade; i; --i)
    {
        while(degrees[i])
        {
            --degrees[i];
            if( !consume(i, i) )
            {
                degrees.clear();
                return false;
            }
        }
    }
    degrees.clear();
    return true;
}


void get_degrees(const char* f_name, vector<int>& v)
{
    ifstream in(f_name);
    int n,m,a,b;
    in>>n>>m;
    v.resize(n, 0);

    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        ++v[a-1];
        ++v[b-1];
    }

}


void Graph::print_dist_BellmanFord(ostream &out, int start, vector<Weigthed_Edge> &edges, int nn)
{
    vector<int> distance(nn+1, 1<<29);
    distance[start] = 0;
    bool ok=true;
    for(int i=1;i<nn &&ok == true;++i)
    {
        ok = false;
        for(auto x: edges)
            if(distance[x.u] + x.weight < distance[x.v])
            {
                distance[x.v] = distance[x.u] + x.weight ;
                ok = true;
            }
    }
    for(auto x: edges)
        if(distance[x.u] + x.weight < distance[x.v])
        {
            out<<"Ciclu negativ!";
            return;
        }
    for(int i=1; i<=nn;++i)
        if(i!=start)
            out<<distance[i]<<' ';
}

void Graph::print_dist_SPFA(ostream &out, int start, vector<vector<pair<int,int>>> &DWG, int nn)
{
    vector<int> nr_updates(nn+1, 0);
    queue<int> candidate_vertices;
    vector<bool> is_candidate(nn+1, false);
    vector<int> distance(nn+1, 1<<29);

    distance[start] = 0;
    candidate_vertices.push(start);
    is_candidate[start] = true;

    int vertex;

    while(candidate_vertices.empty() == false)
    {
        vertex = candidate_vertices.front();
        candidate_vertices.pop();
        is_candidate[vertex] = false;

        ++nr_updates[vertex];
        if(nr_updates[vertex] == nn)
        {
            out<<"Ciclu negativ!";
            return;
        }

        for(auto &w_edge: DWG[vertex]) /// w_edge is a pair (c,v), meaning there is a directed arc from vertex to v with weight c
        {
            if(w_edge.first + distance[vertex] < distance[w_edge.second])
            {


                distance[w_edge.second] = w_edge.first + distance[vertex];
                if(!is_candidate[w_edge.second])
                {
                    candidate_vertices.push(w_edge.second);
                    is_candidate[w_edge.second] = true;
                }
            }
        }
    }


    for(int i=1; i<=nn;++i)
        if(i!=start)
            out<<distance[i]<<' ';
}

void Graph::update_disjoint(int x, vector<int> &father)
{
    if(x!=father[x])
        update_disjoint(father[x], father);
    father[x] = father[father[x]];
}

void  Graph::print_APM_Kruskal(ostream &out, vector<Weigthed_Edge> &edges, int nn) // Will print the total cost of the APM, the number of edges
{                                                                                  // and a list of pairs (x, y) representing the chosen edges
    int nr_chosen = 0, i=0, sum=0;
    int x, y;
    vector<pair<int,int>> chosen_edges;
    vector<int> father(nn+1);
    vector<int> height(nn+1,0);

    for(int k=1; k<=nn; ++k)
        father[k] = k;
    sort(edges.begin(), edges.end());

    while(i<edges.size() && nr_chosen<nn-1)
    {
        x = edges[i].u;
        y = edges[i].v;

        update_disjoint(x, father);
        update_disjoint(y, father);

        if(father[x] != father[y]) /// the nodes are not in the same tree so far
        {
            sum += edges[i].weight;
            ++nr_chosen;
            chosen_edges.push_back(make_pair(edges[i].u, edges[i].v)); /// add edge to the list of selected edges

            if(height[father[x]] > height[father[y]])
                father[father[y]] = father[x];
            else if(height[father[y]] > height[father[x]])
                father[father[x]] = father[y];
            else
            {
                father[father[y]] = father[x];
                ++height[father[x]];
            }
            /*
            if(height[x] > height[y])
                father[y] = x;       /// y becomes a part of x's tree and height of x stays the same
            else if(height[x] < height[y])
                father[x] = y;       /// x becomes a part of y's tree and height of y stays the same
            else
            {
                father[y] = x;       /// the tree of root x and the tree of root y have the same height
                ++height[x];         /// either one can become the main root but the height is increased by 1
            }*/
        }

        ++i;
    }

    out<<sum<<'\n'<<nn-1;
    for(auto edge: chosen_edges)
        out<<'\n'<<edge.first<<' '<<edge.second;
}

void Graph::solve_disjoint(istream &in, ostream &out)
{
    int n,m;
    int op, x, y;
    in>>n>>m;

    vector<int> father(n+1);
    vector<int> height(n+1,0);
    for(int k=1; k<=n; ++k)
        father[k] = k;

    for(int i=0;i<m;++i)
    {
        f>>op>>x>>y;
        update_disjoint(x, father);
        update_disjoint(y, father);
        if(op == 1)
        {
            //father[father[y]] = father[x];
            if(height[father[x]] > height[father[y]])
                father[father[y]] = father[x];
            else if(height[father[y]] > height[father[x]])
                father[father[x]] = father[y];
            else
            {
                father[father[y]] = father[x];
                ++height[father[x]];
            }
        }
        else
        {
            if(father[x] == father[y])
                out<<"DA\n";
            else
                out<<"NU\n";
        }
    }
}


vector<int> Graph::Dijkstra(vector<vector<pair<int,int>>> &DWG, int start_node, int nn, const int inf)
{
    int nod_crt, d;
    vector<int> distance(nn+1, inf);
    distance[start_node] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > min_dist_node;
    min_dist_node.push(make_pair(distance[start_node], start_node));

    while(min_dist_node.empty() == false)
    {
        d = min_dist_node.top().first;
        nod_crt = min_dist_node.top().second;
        min_dist_node.pop();

        if(d == distance[nod_crt])
        {
            for(auto edge:DWG[nod_crt]) /// edge is a pair<int, int> representing (cost, adjacent_vertex)
            {
                if(d + edge.first < distance[edge.second])
                {
                    distance[edge.second] =  d + edge.first;
                    min_dist_node.push(make_pair(distance[edge.second], edge.second));
                }
            }
        }
    }

    return distance;
}

int Graph::TD()
{
    queue<int> q;
    vector<bool> viz(n+1,false);
    vector<int> dist(n+1, 1);

    q.push(1);
    viz[1]=true;
    int nod_crt;
    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin:la[nod_crt])
        {
            if(!viz[nod_vecin])
            {
                viz[nod_vecin]=true;
                q.push(nod_vecin);
            }
        }
    }
    for(int i=1;i<viz.size();++i)
        viz[i]=false;
    q.push(nod_crt);
    viz[nod_crt] = true;
    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin:la[nod_crt])
        {
            if(!viz[nod_vecin])
            {
                viz[nod_vecin]=true;
                q.push(nod_vecin);
                dist[nod_vecin] = dist[nod_crt]+1;
            }
        }
    }
    return dist[nod_crt];
}

void Graph::royFloydWarshall(vector<vector<int>>& distMat, vector<vector<int>>& pred, int inf)
{
    int n = distMat.size();

    for(int k=0; k<n; ++k)
    {
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(distMat[i][j] > distMat[i][k] + distMat[k][j])
                {
                    distMat[i][j] = distMat[i][k] + distMat[k][j];
                    pred[i][j] = pred[k][j];
                }
            }
        }
    }
}


int Graph::max_flow(int n, int source, int terminal, vector<Weigthed_Edge> &DWG)
{
    vector<vector<int>> flow(n+1, vector<int>(n+1,0));   /// acts as a mix of the residual graph and the graph of flow -> positive values = flow;
    vector<vector<int>> capacity(n+1, vector<int>(n+1,0));                                                       /// negative values = reverse flow;
    vector<vector<int>> la(n+1);

    vector<int> pred(n+1, 0);
    vector<bool> visited(n+1, false);

    int maximum_flow=0;

    for(auto& edge:DWG)
    {
        capacity[edge.u][edge.v] = edge.weight;
        if(!capacity[edge.v][edge.u]) /// If i didn't previously encounter a v->u edge
        {                             /// add u and v to each others list for easier bf
            la[edge.u].push_back(edge.v);
            la[edge.v].push_back(edge.u);
        }
    }

    max_flow_bfs(source, terminal, flow, capacity, la, pred, visited);
    while(visited[terminal])
    {
        for(auto& nod_vecin:la[terminal])
        {
            if(flow[nod_vecin][terminal] < capacity[nod_vecin][terminal] && visited[nod_vecin]) /// vertex has been reached and we can make improvements
            {
                int min_flow = capacity[nod_vecin][terminal] - flow[nod_vecin][terminal];
                int nod_crt = nod_vecin;

                while(nod_crt != source) /// find the residual capacity
                {
                    min_flow = min(min_flow, capacity[pred[nod_crt]][nod_crt] - flow[pred[nod_crt]][nod_crt]);
                    nod_crt = pred[nod_crt];                          /// if flow is negative -> reverse edge -> capacity = 0
                }                                                     /// so u end up with abs(flow) in that case;

                flow[nod_vecin][terminal] += min_flow;
                flow[terminal][nod_vecin] -= min_flow;

                maximum_flow += min_flow;

                nod_crt = nod_vecin;
                while(nod_crt != source) /// update flow
                {
                    flow[pred[nod_crt]][nod_crt] += min_flow;
                    flow[nod_crt][pred[nod_crt]] -= min_flow;
                    nod_crt = pred[nod_crt];
                }
            }
        }
        fill(visited.begin(), visited.end(), false);
        max_flow_bfs(source, terminal, flow, capacity, la, pred, visited);
    }
    /// should somehow return last instance of visited for the min-cut;
    /// maybe use maximum_flow as referenced parameter and return viz;
    return maximum_flow;
}

bool Graph::max_flow_bfs(int source, int terminal, vector<vector<int>>& flow, vector<vector<int>>& capacity, vector<vector<int>>& la, vector<int>& pred, vector<bool>& viz)
{
    queue<int> bf_vertices;
    bf_vertices.push(source);

    int nod_crt;

    while(!bf_vertices.empty())
    {
        nod_crt = bf_vertices.front();
        bf_vertices.pop();

        for(auto nod_vecin: la[nod_crt])
        {
            if(flow[nod_crt][nod_vecin] < capacity[nod_crt][nod_vecin] && !viz[nod_vecin])
            {
                viz[nod_vecin] = true;

                if(nod_vecin != terminal)
                {
                    pred[nod_vecin] = nod_crt;
                    bf_vertices.push(nod_vecin);
                }
            }
        }
    }
    return viz[terminal];
}

int Graph::min_hamiltonian_cycle(int n, vector<Weigthed_Edge>& DWG, int inf = 0x1fffffff )
{
    int n2 = 1<<n;
    vector<vector<int>> cost(n,vector<int>(n,inf));
    vector<vector<int>> path_cost(n2, vector<int>(n,inf));  /// path_cost[i][j] = the min cost of a path that ends in vertex j
                                                            /// and contains all vertexes k such that (1<<k) & i = (1<<k);
                                                            /// ~~ k is hashed inside i
                                                            /// min hamiltonian cycle cost becomes min(path_cost[(1<<n)-1][j] + cost[j][i])
                                                            /// for any i chosen arbitrarily and all vertices j such that j->i;
    vector<vector<int>> la(n);

    for(auto& edge: DWG)
    {
        la[edge.v].push_back(edge.u); /// reverse adjacency list to make it easier to find all js described above |^|
        cost[edge.u][edge.v] = edge.weight;
    }

    path_cost[1][0] = 0; /// = path that ends in vertex 0 and only has vertex 0 in it

    for(int i=2; i<n2; ++i)
    {
        for(int j=0; j<n; ++j) /// walk through all vertices to find those in the current path i
        {
            if(i & (1<<j)) /// if j is in path hashed by i compute min path_cost of a path i that end on j
            {
                for(auto k: la[j]) /// there is an edge k->j;
                {
                    if(i & (1<<k)) /// k is also in path i and there is an edge k->j
                        path_cost[i][j] = min(path_cost[i][j], path_cost[i ^ (1<<j)][k] + cost[k][j]);
                        /// min of (current path i to j) and (the path that leads to k and doesn't contain j + cost from k to j)
                        /// since i & (1<<j) is true, i ^ (1<<j) is the same as i - (1<<j) which is smaller than i so it has already been computed
                }
            }
        }
    }
    int min_cost = inf;

    for(auto k:la[0])/// should work with any value from 0 to n-1
        min_cost = min( min_cost, path_cost[n2-1][k] + cost[k][0]);

    return min_cost; /// if there was no hamiltonian cycle min_cost will remain inf so the return value has to be evaluated;
                     /// can't return -1/0 since the graph might as well have negative values;
}

vector<int> Graph::find_eulerian_cycle(int n, vector<pair<int,int>> edges)
{
    vector<int> cycle;
    vector<vector<int>> my_edges(n+1); /// my_edges[i] = the edges that have i as an endpoint - stored as indexes of edges
    vector<bool> available_edges(edges.size(), true); /// available_edges[i]=true if the edge with index i has not been used so far in the cycle
    vector<int> vertices_stack; /// used to avoid stack overflow in recursive dfs;
    //Graph gr(n);

    for(auto i=0; i<edges.size(); ++i)
    {
        //gr.add_edge(edges[i].first ,edges[i].second);
        //gr.add_edge(edges[i].second,edges[i].first);
        my_edges[edges[i].first].push_back(i);
        my_edges[edges[i].second].push_back(i);
    }
    //if(gr.nr_conexe_dfs()>1)
        //return cycle;

    for(auto i=1; i<=n; ++i)
        if(my_edges[i].size() & 1) /// vertex i has an odd number of edges -> there is no eulerian cycle
            return cycle;


    vertices_stack.push_back(1);

    while(!vertices_stack.empty())
    {
        auto crt_node = vertices_stack.back(); /// take the last vertex === top of the stack

        if(my_edges[crt_node].size()) /// if the current vertex still has edges
        {
            auto edge_index = my_edges[crt_node].back(); /// take the last edge since it's easier to remove with pop_back() after it's used
            my_edges[crt_node].pop_back();

            if(available_edges[edge_index]) /// if the edge hasn't been used already (by the vertex at the other end of it)
            {
                available_edges[edge_index] = false;
                auto next_node = crt_node ^ edges[edge_index].first ^ edges[edge_index].second;
                        /// either edges[edge_index].second or edges[edge_index].first has to be = to crt_node
                        /// and by using xor they cancel out;
                        /// alternative: next_node = (crt_node == edges[edge_index].second)? edges[edge_index].first : edges[edge_index].second

                vertices_stack.push_back(next_node);
            }
        }
        else
        {
            vertices_stack.pop_back();
            cycle.push_back(crt_node);
        }
    }


    return cycle; /// cycle[i] - cycle[i+1] represents an edge
                 /// last vertex is the same as the first vertex
}


int main()
{
    int n,m;
    int a,b,c;

    f>>n>>m;
    vector<Weigthed_Edge> muchii;

    for(int i=0;i<m;++i)
    {
        f>>a>>b>>c;
        muchii.push_back(Weigthed_Edge(a,b,c));
    }


    g<<Graph::max_flow(n,1,n,muchii);


    return 0;
}