#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int Ni = 210;
const int MAX = 1<<26;
struct Edge{
int u,v,c;
int next;
}edge[20*Ni];
int n,m;
int edn;//边数
int p[Ni];//父亲
int d[Ni];
int sp,tp;//原点，汇点
void addedge(int u,int v,int c)
{
edge[edn].u=u; edge[edn].v=v; edge[edn].c=c;
edge[edn].next=p[u]; p[u]=edn++;
edge[edn].u=v; edge[edn].v=u; edge[edn].c=0;
edge[edn].next=p[v]; p[v]=edn++;
}
int bfs()
{
queue <int> q;
memset(d,-1,sizeof(d));
d[sp]=0;
q.push(sp);
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=p[cur];i!=-1;i=edge[i].next)
{
int u=edge[i].v;
if(d[u]==-1 && edge[i].c>0)
{
d[u]=d[cur]+1;
q.push(u);
}
}
}
return d[tp] != -1;
}
int dfs(int a,int b)
{
int r=0;
if(a==tp)return b;
for(int i=p[a];i!=-1 && r<b;i=edge[i].next)
{
int u=edge[i].v;
if(edge[i].c>0 && d[u]==d[a]+1)
{
int x=min(edge[i].c,b-r);
x=dfs(u,x);
r+=x;
edge[i].c-=x;
edge[i^1].c+=x;
}
}
if(!r)d[a]=-2;
return r;
}
int dinic(int sp,int tp)
{
int total=0,t;
while(bfs())
{
while(t=dfs(sp,MAX))
total+=t;
}
return total;
}
int main()
{
int i,u,v,c;
while(~scanf("%d%d",&m,&n))
{
edn=0;//初始化
memset(p,-1,sizeof(p));
sp=1;tp=n;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
addedge(u,v,c);
}
printf("%d\n",dinic(sp,tp));
}
return 0;
}
const int oo=1e9; //无穷
const int mm=11111111; //边
const int mn=888888; //点
int node,src,dest,edge;
int ver[mm],flow[mm],cost[mm],nex[mm];
int head[mn],dis[mn],p[mn],q[mn],vis[mn];
/**这些变量基本与最大流相同，增加了
cost 表示边的费用，
p 记录可行流上节点对应的反向边
*/
void prepare(int _node,int _src,int _dest) //预处理 点的个数 起点 终点
{
node=_node,src=_src,dest=_dest;
for(int i=0; i<node; i++)head[i]=-1,vis[i]=0;
edge=0;
}
void addedge(int u,int v,int f,int c)
{
ver[edge]=v,flow[edge]=f,cost[edge]=c,nex[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,cost[edge]=-c,nex[edge]=head[v],head[v]=edge++;
}
/**以上同最大流*/
/**spfa 求最短路，并用 p 记录最短路上的边*/
bool spfa()
{
int i,u,v,l,r=0,tmp;
for(i=0; i<node; ++i)dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for(l=0; l!=r; (++l>=mn)?l=0:l)
for(i=head[u=q[l]],vis[u]=0; i>=0; i=nex[i])
if(flow[i]&&dis[v=ver[i]]>(tmp=dis[u]+cost[i]))
{
dis[v]=tmp;
p[v]=i^1;
if(vis[v]) continue;
vis[q[r++]=v]=1;
if(r>=mn)r=0;
}
return p[dest]>-1;
}
/**源点到汇点的一条最短路即可行流，不断的找这样的可行流*/
int SpfaFlow()
{
int i,ret=0,delta;
while(spfa())
{
for(i=p[dest],delta=oo; i>=0; i=p[ver[i]])
if(flow[i^1]<delta)delta=flow[i^1];
for(i=p[dest]; i>=0; i=p[ver[i]])
flow[i]+=delta,flow[i^1]-=delta;
ret+=delta*dis[dest];
}
return ret;
}
#include<bits/stdc++.h>
using namespace std;
namespace MCMF {
int INF=1<<29;
const int MX=605;
int S, T;//源点，汇点
int erear, n;
int st, en, maxflow, mincost;
bool vis[MX];
int Head[MX], cur[MX], dis[MX];
const int ME = 4e5 + 5;//边的数量
queue <int> Q;
struct Edge {
int v, cap, cost, nxt, flow;
Edge() {}
Edge(int a, int b, int c, int d) {
v = a, cap = b, cost = c, nxt = d, flow = 0;
}
} E[ME], SE[ME];
void init(int _n) {
n = _n, erear = 0;
for(int i = 0; i <= n; i++) Head[i] = -1;
}
void addedge(int u, int v, int cap, int cost) {
E[erear] = Edge(v, cap, cost, Head[u]);
Head[u] = erear++;
E[erear] = Edge(u, 0, -cost, Head[v]);
Head[v] = erear++;
}
bool adjust() {
int v, min = INF;
for(int i = 0; i <= n; i++) {
if(!vis[i]) continue;
for(int j = Head[i]; ~j; j = E[j].nxt) {
v = E[j].v;
if(E[j].cap - E[j].flow) {
if(!vis[v] && dis[v] - dis[i] + E[j].cost < min) {
min = dis[v] - dis[i] + E[j].cost;
}
}
}
}
if(min == INF) return false;
for(int i = 0; i <= n; i++) {
if(vis[i]) {
cur[i] = Head[i];
vis[i] = false;
dis[i] += min;
}
}
return true;
}
int augment(int i, int flow) {
if(i == en) {
mincost += dis[st] * flow;
maxflow += flow;
return flow;
}
vis[i] = true;
for(int j = cur[i]; j != -1; j = E[j].nxt) {
int v = E[j].v;
if(E[j].cap == E[j].flow) continue;
if(vis[v] || dis[v] + E[j].cost != dis[i]) continue;
int delta = augment(v, std::min(flow, E[j].cap - E[j].flow));
if(delta) {
E[j].flow += delta;
E[j ^ 1].flow -= delta;
cur[i] = j;
return delta;
}
}
return 0;
}
void spfa() {
int u, v;
for(int i = 0; i <= n; i++) {
vis[i] = false;
dis[i] = INF;
}
Q.push(st);
dis[st] = 0; vis[st] = true;
while(!Q.empty()) {
u = Q.front(), Q.pop(); vis[u] = false;
for(int i = Head[u]; ~i; i = E[i].nxt) {
v = E[i].v;
if(E[i].cap == E[i].flow || dis[v] <= dis[u] + E[i].cost) continue;
dis[v] = dis[u] + E[i].cost;
if(!vis[v]) {
vis[v] = true;
Q.push(v);
}
}
}
for(int i = 0; i <= n; i++) {
dis[i] = dis[en] - dis[i];
}
}
int zkw(int s, int t, int &ret_flow) {
st = s, en = t;
spfa();
mincost = maxflow = 0;
for(int i = 0; i <= n; i++) {
vis[i] = false;
cur[i] = Head[i];
}
do {
while(augment(st, INF)) {
memset(vis, false, n * sizeof(bool));
}
} while(adjust());
ret_flow = maxflow;
return mincost;
}
void out(int pp){
for(int i=0;i<pp;i+=2){
if(E[i].flow==E[i].cap)printf("%d ",i/2+1);
}
printf("\n");
}
}
int main()
{
int ds,i,n,m;
scanf("%d%d%d",&n,&m,&ds);
MCMF::init(n+m+5);
for(i=1;i<=ds;i++){
int x,y,z,zz;scanf("%d%d",&x,&y);
MCMF::addedge(x,y+n,1,1);
}
for(i=1;i<=n;i++){
MCMF::addedge(0,i,2,-1300);
MCMF::addedge(0,i,1e7,0);
}
for(i=1;i<=m;i++){
MCMF::addedge(i+n,n+m+1,2,-1300);
MCMF::addedge(i+n,n+m+1,1e7,0);
}
/* MCMF::addedge(n+m+2,0,1e8,0);
MCMF::addedge(0,n+m+1,1e8,0);
printf("%d\n",1300+MCMF::zkw(0,n+m+1,m)00);最小费用流 */
printf("%d\n",1300+MCMF::zkw(0,n+m+1,m)00);
MCMF::out(ds*2);
return 0;
}
