#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAX_N 1024

vector <int> vec[MAX_N];
int n, m, i, j, p, q, cpct, improve;
int c[MAX_N][MAX_N], ind[MAX_N][MAX_N];
int Q[MAX_N], flux[MAX_N], tata[MAX_N], d[MAX_N], sol[MAX_N];

void cit() {
    freopen("critice.in", "r", stdin);
    freopen("critice.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &p, &q, &cpct);
        ind[p][q] = ind[q][p] = i;
        
        vec[p].push_back(q);
        vec[q].push_back(p);
        
        c[p][q] = cpct;
        c[q][p] = cpct;
    }
}

void bfs() {
    int st = 0, dr = 1;
    
    flux[1] = 2147000000; 
    while (st < dr) {
        st++;
        
        int len = vec[Q[st]].size();
        for (j = 0; j < len; j++) {
            i = vec[Q[st]][j];
            if (flux[i] == 0 && c[Q[st]][i]) {
                int x = c[Q[st]][i];
                if (flux[Q[st]] < c[Q[st]][i])
                    x = flux[Q[st]];
                    
                flux[i] = x;
                tata[i] = Q[st];
                
                Q[++dr] = i;
            }
            if (flux[n]) break;            
        }
        if (flux[n]) break;        
    }
            
    improve = flux[n];
    
    if (!improve) return;
    
    int x = n;
    while (x != 1) {
        c[tata[x]][x] -= flux[n];
        c[x][tata[x]] += flux[n];
        
        x = tata[x];
    }
}

void dfs(int nod, int tip, int viz) {
    d[nod] = viz;
    
    int len = vec[nod].size();
    for (int j = 0; j < len; j++) {
        i = vec[nod][j];
        if (tip == 1) {
            if (c[nod][i] != 0 && !d[i])
                dfs(i, tip, viz);
        }
        else {
            if (c[i][nod] != 0 && !d[i])
                dfs(i, tip, viz);
        }
    }
}

int main() {
    
    cit();
    
    improve = 1;
    while (improve) {
        Q[1] = 1;
        bfs();
        
        memset(Q, 0, sizeof(Q));
        memset(flux, 0, sizeof(flux));
        memset(tata, 0, sizeof(tata));
    }
    
/*    dfs(1, 1, 1);
    dfs(n, 0, 2);

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (d[i] == 1 && d[j] == 2 && c[i][j] == 0 && c[j][i] != 0)
                sol[++sol[0]] = ind[i][j];

    printf("%d\n", sol[0]);
    for (i = 1; i <= sol[0]; i++)
        printf("%d\n", sol[i]); */

    return 0;
}