#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <cstring>
class InParser
{
private:
FILE* fin;
char* buffer;
size_t SIZE = 4096;
int buffer_index;
char get_char()
{
++buffer_index;
if(buffer_index == (int)SIZE)
{
size_t count = fread(buffer, 1, SIZE, fin);
if(count < SIZE)
buffer[count] = 0;
buffer_index = 0;
}
return buffer[buffer_index];
}
public:
InParser(const char* name)
{
fin = fopen(name, "r");
buffer = new char[SIZE];
memset(buffer, 0, SIZE);
buffer_index = SIZE - 1;
}
~InParser()
{
fclose(fin);
delete[] buffer;
}
InParser& operator>>(int& x)
{
char c;
while(!isdigit(c = get_char()))
;
x = c - '0';
while(isdigit(c = get_char()))
x = x * 10 + c - '0';
return *this;
}
};
class OutParser
{
private:
FILE* fout;
char* buffer;
int buffer_index;
const int SIZE = 4096;
void print_char(char c)
{
if(buffer_index == SIZE)
{
fwrite(buffer, 1, SIZE, fout);
buffer_index = 0;
}
buffer[buffer_index++] = c;
}
public:
OutParser(const char* name)
{
fout = fopen(name, "w");
buffer_index = 0;
buffer = new char[SIZE];
memset(buffer, 0, SIZE);
}
~OutParser()
{
fwrite(buffer, 1, buffer_index, fout);
fclose(fout);
delete[] buffer;
}
OutParser& operator<<(int x)
{
if(x < 10)
print_char('0' + x);
else
{
*this << x / 10;
print_char('0' + x % 10);
}
return *this;
}
OutParser& operator<<(char c)
{
print_char(c);
return *this;
}
};
InParser fin("critice.in");
OutParser fout("critice.out");
/* clang-format off */
static __attribute__((unused)) void redir(const std::string str) { std::freopen((str + ".in").c_str(), "r", stdin); std::freopen((str + ".out").c_str(), "w", stdout); }
static void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); }
template<typename T, typename... Ts> static void read(T& var, Ts&... vars) { read(var); read(vars...); }
/* clang-format on */
struct pair_hash
{
template<class T1, class T2>
std::size_t operator()(const std::pair<T1, T2>& pair) const
{
return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
}
};
using adj_t = std::vector<std::vector<std::pair<int, int>>>;
using mat_t = std::vector<std::vector<int>>;
using uset = std::unordered_set<int>;
static adj_t adj;
static std::unordered_map<std::pair<int, int>, int, pair_hash> edges_idx;
static int N;
static int M;
static void dfs(const int src, std::vector<char>& vis, uset& p, bool inverted,
const mat_t& capacity, const mat_t& flow)
{
vis[src] = true;
p.insert(src);
for(const auto& e : adj[src])
{
const int v = e.first;
if(vis[v])
{
continue;
}
if(!inverted && flow[src][v] == capacity[src][v])
{
continue;
}
if(inverted && flow[v][src] == capacity[v][src])
{
continue;
}
dfs(v, vis, p, inverted, capacity, flow);
}
};
static void maxflow(const int src, const int dest)
{
mat_t capacity(N + 1, std::vector<int>(N + 1, 0));
mat_t flow(N + 1, std::vector<int>(N + 1, 0));
for(int node = 1; node <= N; ++node)
{
for(const auto& e : adj[node])
{
capacity[node][e.first] = std::max(capacity[node][e.first], e.second);
}
}
const auto bfs_parents = [&]() -> std::vector<int>
{
std::vector<char> visited(N + 1, false);
std::vector<int> parent(N + 1, -1);
std::queue<int> q;
q.push(src);
visited[src] = true;
while(!q.empty())
{
const auto current = q.front();
q.pop();
for(const auto& neigh : adj[current])
{
if(visited[neigh.first] || capacity[current][neigh.first] <=
flow[current][neigh.first])
{
continue;
}
if(neigh.first == dest)
{
parent[dest] = current;
return parent;
}
q.push(neigh.first);
parent[neigh.first] = current;
visited[neigh.first] = true;
}
}
return parent;
};
while(true)
{
const auto parent = bfs_parents();
if(parent[dest] == -1)
{
break;
}
int path_min_cap = INT_MAX;
for(int v = dest; v != src; v = parent[v])
{
const int u = parent[v];
path_min_cap = std::min(path_min_cap, capacity[u][v] - flow[u][v]);
}
for(int v = dest; v != src; v = parent[v])
{
const int u = parent[v];
flow[u][v] += path_min_cap;
flow[v][u] -= path_min_cap;
}
}
std::vector<char> visited(N + 1, false);
uset left;
uset right;
dfs(1, visited, left, false, capacity, flow);
dfs(N, visited, right, true, capacity, flow);
std::vector<int> solution;
for(const int u : left)
{
for(const auto& e : adj[u])
{
const int v = e.first;
if(flow[u][v] == capacity[u][v] && right.find(v) != right.end())
{
solution.push_back(edges_idx[std::make_pair(u, v)]);
}
}
}
std::sort(solution.begin(), solution.end());
fout << (int)solution.size() << '\n';
for(int el : solution)
{
fout << el << '\n';
}
}
int main()
{
fin >> N;
fin >> M;
adj.resize(N + 1);
for(int i = 0; i < M; ++i)
{
int u, v, w;
fin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edges_idx[std::make_pair(u, v)] = i + 1;
edges_idx[std::make_pair(v, u)] = i + 1;
}
maxflow(1, N);
}