#include <bits/stdc++.h>

using namespace std;

map < string, int > codes;
vector < int > father;
vector < bool > seen;
vector < string > nodes;
vector < pair < pair < string, string >, int > > listEdges;
vector < vector < int > > graph, capacity, flow;

ifstream fin("maxflow.in");

void readGraph() {
  int numEdg;
  int gunoi;
  fin >> gunoi >> numEdg;
  for (int i = 0; i < numEdg; ++i) {
    string a, b;
    int c;
    fin >> a >> b >> c;
    listEdges.push_back(make_pair(make_pair(a, b), c));
    if (codes.find(a) == codes.end()) {
      codes[a] = (int) nodes.size();
      nodes.push_back(a);
    }
    if (codes.find(b) == codes.end()) {
      codes[b] = (int) nodes.size();
      nodes.push_back(b);
    }
  }

  father.resize(nodes.size());
  seen.resize(nodes.size());
  graph.resize(nodes.size());
  capacity.resize(nodes.size());
  flow.resize(nodes.size());
  for (int i = 0; i < (int) nodes.size(); ++i) {
    capacity[i].resize(nodes.size());
    flow[i].resize(nodes.size());
  }

  for (auto edg : listEdges) {
    int x = codes[edg.first.first];
    int y = codes[edg.first.second];
    capacity[x][y] += edg.second;
    if (find(graph[x].begin(), graph[x].end(), y) == graph[x].end()) {
      graph[x].push_back(y);
    }
    if (find(graph[y].begin(), graph[y].end(), x) == graph[y].end()) {
      graph[y].push_back(x);
    }
  }
}

bool BFS(int source, int sink) {
  seen.assign(nodes.size(), false);
  queue < int > q;
  q.push(source);
  seen[source] = true;

  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    if (curr != sink) {
      for (auto ngh : graph[curr]) {
        if (!seen[ngh] && flow[curr][ngh] < capacity[curr][ngh]) {
          seen[ngh] = true;
          q.push(ngh);
          father[ngh] = curr;
        }
      }
    }
  }
  return seen[sink];
}

int maxflow(int source, int sink) {
  int mxflow = 0;
  while (BFS(source, sink)) {
    for (auto sink_ngh : graph[sink]) {
      if (seen[sink_ngh]) {
        father[sink] = sink_ngh;
        int fl = INT_MAX;

        for (int curr = sink; curr != source; curr = father[curr]) {
          fl = min(fl, capacity[father[curr]][curr] - flow[father[curr]][curr]);
        }
        mxflow += fl;

        for (int curr = sink; curr != source; curr = father[curr]) {
          flow[father[curr]][curr] += fl;
          flow[curr][father[curr]] -= fl;
        }
      }
    }
  }
  return mxflow;
}

int main()
{
    readGraph();

    ofstream fout("maxflow.out");
    string source_code = "1", sink_code = "";
    int n = (int) nodes.size();
    do {
      sink_code += '0' + n % 10;
      n /= 10;
    } while (n > 0);
    reverse(sink_code.begin(), sink_code.end());
    fout << maxflow(codes[source_code], codes[sink_code]) << endl;
    return 0;
}