#include <iostream>
#include <fstream>
#include <vector>
#include <queue> 
#include <climits>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int BFS(int& n, int& source, int& target, vector<vector<int>>& capacity, vector<vector<int>>& ad_list, vector<int>& path)
{
    vector<bool> visited(n+1, false);
    queue<pair<int, int>> bfs_q;
    bfs_q.push({source, INT_MAX});
    visited[source] = true;
    int min_flow;

    while(!bfs_q.empty())
    {
        int curr_v = bfs_q.front().first;
        int curr_flow = bfs_q.front().second;
        path.push_back(curr_v); 
        bfs_q.pop();
        
        for(auto next : ad_list[curr_v])
            if(!visited[next] && capacity[curr_v][next] > 0)
            {
                visited[next] = true;               
                min_flow = min(curr_flow, capacity[curr_v][next]);

                if(next == target)
                {
                    return min_flow;
                }

                bfs_q.push({next, min_flow});
            }
    }

   return 0;
}

int main()
{
    int n, m, flow, source, target;
    vector<vector<int>> capacity(n+1, vector<int>(n+1));
    vector<vector<int>> ad_list(n+1);
    vector<int> path;

    fin >> n >> m;
    
    flow = 0;
    source = 1;
    target = n;

    for(int i = 1; i <=m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        ad_list[x].push_back(y);
        ad_list[y].push_back(x);
        capacity[x][y] = c;
    }
    
    while(true)
    {
        int min_flow = BFS(n, source, target, capacity, ad_list, path);
        if(min_flow == 0)
            break;
        flow += min_flow;

        int child = target;
        for(int index = path.size() -1; index >= 0; index--)
        {
            cout << path[index] << " ";
            capacity[path[index]][child] -= min_flow;
            capacity[child][path[index]] += min_flow;
            child = path[index];
        }

        path.clear();
    }

    fout << flow;

    return 0;
}