#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#define INF 0x3f3f3f3f
using namespace std;
vector<vector<int>> Cost, Flow, Capacity;
vector<vector<pair<int,int>>> Graph;
vector<int> oldDist, realDist, DP, daddy;
void addEdge(int from, int to, int index, int capacity, int cost)
{
Graph[from].emplace_back(to, index);
Cost[from][to] = cost;
Capacity[from][to] = capacity;
}
void bellmanFord(int k, int superSink, int N, int M)
{
vector<bool> inQ;
queue<int> Q;
inQ.resize(N+M+2);
fill(oldDist.begin(), oldDist.end(), INF);
inQ[k] = true;
Q.push(k);
oldDist[k] = 0;
while (!Q.empty()) {
k = Q.front();
Q.pop();
inQ[k] = false;
if (k == superSink)
continue;
for (auto it: Graph[k]) {
int v = it.first;
if (oldDist[v] > oldDist[k] + Cost[k][v] && Capacity[k][v] > Flow[k][v]) {
oldDist[v] = oldDist[k] + Cost[k][v];
if (inQ[v])
continue;
inQ[v] = true;
Q.push(v);
}
}
}
}
bool dijkstra(int k, int superSink)
{
priority_queue<pair<int,int>> Q;
fill(realDist.begin(), realDist.end(), INF);
fill(DP.begin(), DP.end(), INF);
realDist[k] = 0;
DP[k] = 0;
Q.push({-0, k});
int cost;
while (!Q.empty()) {
tie(cost, k) = Q.top();
cost = -cost;
Q.pop();
if (DP[k] < cost)
continue;
if (k == superSink)
continue;
// oldDist[v] <= oldDist[k] + Cost[k][v] <=> Cost[k][v] + (oldDist[k] - oldDist[v]) >= 0
for (auto it: Graph[k]) {
int v = it.first;
if (DP[v] > DP[k] + Cost[k][v] + (oldDist[k] - oldDist[v]) && Capacity[k][v] > Flow[k][v]) {
DP[v] = DP[k] + Cost[k][v] + (oldDist[k] - oldDist[v]);
realDist[v] = realDist[k] + Cost[k][v];
daddy[v] = k;
Q.push({-DP[v], v});
}
}
}
oldDist = realDist;
return realDist[superSink] != INF;
}
int main()
{
ifstream fin("cmcm.in");
ofstream fout("cmcm.out");
ios::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
int N, M, E;
fin >> N >> M >> E;
Graph.resize(N + M + 2);
Cost.resize(N + M + 2);
Flow.resize(N + M + 2);
Capacity.resize(N + M + 2);
fill(Cost.begin(), Cost.end(), vector<int>(N + M));
fill(Capacity.begin(), Capacity.end(), vector<int>(N + M));
fill(Flow.begin(), Flow.end(), vector<int>(N + M));
oldDist.resize(N + M + 2);
realDist.resize(N + M + 2);
DP.resize(N + M + 2);
daddy.resize(N + M + 2);
for (int i = 0; i < M; ++i) {
int a, b, cost;
fin >> a >> b >> cost;
-- a;
-- b;
addEdge(a, b + N, i + 1, 1, cost);
addEdge(b + N, a, i + 1, 0, -cost);
}
int superStart = N + M;
int superSink = N + M + 1;
for (int i = 0; i < N; ++i)
addEdge(superStart, i, -1, 1, 0);
for (int i = 0; i < M; ++i)
addEdge(i + N, superSink, -1, 1, 0);
int maxFlow = 0;
int minCost = 0;
bellmanFord(superStart, superSink, N, M);
while (dijkstra(superStart, superSink)) {
int bottleNeck = INF;
for (int k = superSink; k != superStart && bottleNeck > 0; k = daddy[k])
bottleNeck = min(bottleNeck, Capacity[daddy[k]][k] - Flow[daddy[k]][k]);
if (bottleNeck == 0) continue;
for (int k = superSink; k != superStart; k = daddy[k]) {
Flow[daddy[k]][k] += bottleNeck;
Flow[k][daddy[k]] -= bottleNeck;
}
minCost += bottleNeck * realDist[superSink];
maxFlow += bottleNeck;
}
fout << maxFlow << " " << minCost << "\n";
for (int k = 0; k < N; ++k)
for (auto it: Graph[k]) {
int v = it.first;
if (Flow[k][v] == 1)
fout << it.second << " ";
}
fout << "\n";
return 0;
}