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

const int maxN = 1001;

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[], bool visited[]);

int main()
{
    int N, M, i, x, y ,c;
    ifstream f("maxflow.in");
    f >> N >> M;
    vector<int> adjList[N + 1];
    int flow[N + 1][maxN], capacity[N + 1][maxN], parent[N + 1];
    bool visited[N + 1];
    for (i = 1; i <= N; i++)
    {
        fill(flow[i] + 1, flow[i] + N + 1, 0);
        fill(capacity[i] + 1, capacity[i] + N + 1, 0);
    }

    for (i = 1; i <= M; i++)
    {
        f >> x >> y >> c;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
        capacity[x][y] = c;
    }

    int minFlow, result = 0;
    int j, currentNode;
    while (BFS(1, N, adjList, flow, capacity, parent, visited))
    {
        cout << adjList[N].size() << " ";
        for (j = 0; j < adjList[N].size(); j++)
        {
            currentNode = adjList[N][j];
            if (flow[currentNode][N] != capacity[currentNode][N] && visited[currentNode])
            {
                minFlow = INT_MAX;
                parent[N] = currentNode;
                for (i = N; parent[i] != -1; i = parent[i])
                    minFlow = min(minFlow, capacity[parent[i]][i] - flow[parent[i]][i]);

                if (minFlow)
                {
                    for (i = N; parent[i] != -1; i = parent[i])
                    {
                        flow[parent[i]][i] += minFlow;
                        flow[i][parent[i]] -= minFlow;
                    }

                    result += minFlow;
                }
            }
        }
    }

    ofstream g("maxflow.out");
    g << result;
    g.close();

    return 0;
}

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[], bool visited[])
{
    fill(visited + 1, visited + N + 1, false);

    queue<int> q;
    q.push(src);
    visited[src] = true;
    parent[src] = -1;

    int x, i;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        if (x != N)
        {
            for (i = 0; i < adjList[x].size(); i++)
            {
                int neighbor = adjList[x][i];
                if (capacity[x][neighbor] != flow[x][neighbor] && !visited[neighbor])
                {
                    visited[neighbor] = true;
                    q.push(neighbor);
                    parent[neighbor] = x;
                }
            }
        }
    }

    return visited[N];
}