#include <fstream>
#include <vector>
#include <queue>
#include <random>
#include <ctime>
#include <functional>
using namespace std;
ifstream cin("maxflow.in");
ofstream cout("maxflow.out");
class FLUX
{
    vector<vector<int>>flux,cap;
    vector<vector<int>>a;
    vector<int>t;
    bool bfs(const int s,int d)
    {
        fill(t.begin(),t.end(),-1);
        queue<int>q;
        q.push(s);
        while(q.size())
        {
            int acm=q.front();
            q.pop();
            for(auto &c:a[acm])
            {
                if(c==s || t[c]!=-1 || flux[acm][c]==cap[acm][c])
                {
                    continue;
                }
                t[c]=acm;
                if(c!=d)q.push(c);
            }
        }
        return (t[d]!=-1);
    }
public:
    FLUX(int n)
    {
        flux=cap=vector<vector<int>>(n,vector<int>(n,0));
        a=vector<vector<int>>(n);
        t=vector<int>(n);
    }
    void add_edge(int x,int y,int capp)
    {
        cap[x][y]=capp;
        a[x].push_back(y);
        a[y].push_back(x);
        //cout<<x<<' '<<y<<'\n';
    }
    int get_ans(const int s,int d)
    {
        int rez=0;
        while(bfs(s,d))
        {
            //cout<<"da";
            for(auto &c:a[d])
            {
                t[d]=c;
                int aux=d,val=2e9;
                while(t[aux]!=-1)
                {
                    val=min(cap[t[aux]][aux]-flux[t[aux]][aux],val);
                    aux=t[aux];
                }
                if(s!=aux)
                {
                    continue;
                }
                aux=d;
                while(t[aux]!=-1)
                {
                    flux[t[aux]][aux]+=val;
                    flux[aux][t[aux]]-=val;
                    aux=t[aux];
                }
                rez+=val;
            }
        }
        return rez;
    }
};
namespace Solver {
    // Aici poti scrie codul
    int solve(int n, int m, std::vector< std::vector<int> >p)
    {

        srand(time(0));
        vector<vector<uint64_t>>sum(n,vector<uint64_t>(m+1,0));
        vector<uint64_t>pow(m+1,1);
        uint64_t sigma=2017;
        for(int i=2;i<=m;i++)
        {
            pow[i]=pow[i-1]*sigma;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                sum[i][j]=sum[i][j-1]+pow[j]*p[i][j-1];
            }
        }
        auto dif=[&](int x,int y)->bool
        {
            int st=0,dr=m,l=0,r=m+1;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                if(sum[x][mid]==sum[y][mid])
                {
                    l=mid;
                    st=mid+1;
                }
                else
                {
                    dr=mid-1;
                }
            }
            st=1,dr=m;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                if(sum[x][m]-sum[x][mid-1]==sum[y][m]-sum[y][mid-1])
                {
                    r=mid;
                    dr=mid-1;
                }
                else
                {
                    st=mid+1;
                }
            }

            return (sum[x][r-2]-sum[x][l+1]==sum[y][r-2]-sum[y][l+1]);
        };
        auto dif2=[&](int x,int y)
        {
            int rez=0;
            for(int i=0;i<m;i++)
            {
                if(p[x][i]!=p[y][i])rez++;
            }
            return (rez==2);
        };
        FLUX flux(n+2);
        vector<vector<int>>g(n);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(dif(i,j))
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }

        vector<bool>ok(n,0);
        int s=n,d=n+1;
        function<void(int,bool)>dfs=[&](int nod,bool x)
        {
            ok[nod]=1;
            if(x)
            {
                flux.add_edge(nod,d,1);
            }
            else
            {
                flux.add_edge(s,nod,1);
            }
            for(auto &c:g[nod])
            {
                if(!ok[c])
                {
                    flux.add_edge(nod,c,1);
                    dfs(c,(x^1));
                }
            }
        };
        for(int i=0;i<n;i++)
        {
            if(!ok[i])
            {
                dfs(i,0);
            }
        }
        return n-flux.get_ans(s,d);

    }
}

main() {

    int n,m;
    cin>>n>>m;
    FLUX flux(n);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        flux.add_edge(x-1,y-1,c);
    }
    cout<<flux.get_ans(0,n-1);
    return 0;
    //int n, m;
    cin >> n >> m;
    vector< vector<int> > p(n, vector<int>(m));
    for (int i = 0; i < n; i++)	{
        for (int j = 0; j < m; j++) {
            cin >> p[i][j];
        }
    }

    int result = Solver::solve(n, m, p);

    cout << result << '\n';
    return 0;
}