//SURSA CU DFS SI SCALING

#include <fstream>
#include <vector>

using namespace std;


ifstream in("maxflow.in");
ofstream out("maxflow.out");
int n, m, cmax;
vector<pair<int, int>> v[1005];
pair<int, int> lat[10005];
vector<int> st;
int viz[1005];
int ok, ans;

void dfs(int nod, int xmin, int cmin)
{
    viz[nod] = 1;

    if(nod == n)
    {
        ok = 1;
        ans += xmin;
        for(auto it: st)
        {
            if(lat[it].second > 0)
            {
                lat[it].first += xmin;
                lat[it + 1].first -= xmin;
            }
            else
            {
                lat[it].first += xmin;
                lat[it - 1].first -= xmin;
            }
        }

        return;
    }

    for(auto it: v[nod])
    {
        if(ok == 1)
        {
            return;
        }
        if(viz[it.first] == 0 && lat[it.second].second - lat[it.second].first >= cmin)
        {
            st.push_back(it.second);

            dfs(it.first, min(xmin, lat[it.second].second - lat[it.second].first), cmin);

            st.pop_back();
        }
    }
}

int main()
{
    in>>n>>m;

    int x, y, c;
    for(int i = 1; i<=2*m; i++)
    {
        in>>x>>y>>c;

        v[x].push_back({y, i});
        lat[i].first = 0;
        lat[i].second = c;

        i++;
        v[y].push_back({x, i});
        lat[i].first = 0;
        lat[i].second = 0;

        cmax = max(cmax, c);
    }

    for(int i = c; i>=1; i/=2)
    {
        ok = 1;
        while(ok == 1)
        {
            ok = 0;

            for(int i = 1; i<=n; i++)
            {
                viz[i] = 0;
            }
            st.clear();

            dfs(1, 9999999, i);
        }
    }

    out<<ans;

    return 0;
}