#include <bits/stdc++.h>
using namespace std;

const int nmax = 1007;
typedef long long llong;

int n, m;
vector<int> adj[nmax];
int cap[nmax][nmax];
int flow[nmax][nmax];
int par[nmax];

void bfs() {

  queue<int> q;
  q.push(1);

  while (!q.empty()) {
    int u = q.front(); q.pop();
    cout << u << ' ';
    for (int v : adj[u]) {
      if (v != 1 && par[v] == 0 && flow[u][v] < cap[u][v]) {
        par[v] = u;
        q.push(v);
      }
    }
  }
  cout << endl;

}

void solve() {

  cin >> n >> m;
  
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    adj[u].push_back(v);
    adj[v].push_back(u);
    cap[u][v] = cap[v][u] = c;
    flow[v][u] = c;
  }

  llong totalFlow = 0;

  for (;;) {

    memset(par, 0, sizeof(par));

    bfs();

    if (par[n]) {

      int currentFlow = INT_MAX;

      for (int u = n; u != 1; u = par[u]) {
        currentFlow = min(currentFlow, cap[par[u]][u] - flow[par[u]][u]);
      }
      
      for (int u = n; u != 1; u = par[u]) {
        flow[par[u]][u] += currentFlow;
        flow[u][par[u]] -= currentFlow;
      }

      totalFlow += currentFlow;

    } else break;
  
  }

  cout << totalFlow << endl;

}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("maxflow.in", "r", stdin);
  freopen("maxflow.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();
}