Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,id;

#define MAXN 510

#define MAXM 810

struct edges

{

	int u,v,w;

}es[MAXM];

#define MAXP MAXN

#define MAXE (MAXM * 2)

struct edge

{

    int to,nxt;

    int f;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b,int f)

{//cout << a << " " << b << " " << f << endl;

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

int S,T;

#define INF 0x3f3f3f3f

int ch[MAXP];

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[S] = 0;

    queue<int> q;q.push(S);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[T] != -1);

}

int flow(int k,int f)

{

    if(k == T)return f;

    int r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f)

        {

            int l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

int dinic()

{

    int ans = 0,r;

    while(BFS())while(r = flow(S,INF))ans += r;

    return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d%d",&n,&m,&id);

	int val;

	for(int i = 1;i <= m;++i)

	{

		es[i].u = rd();es[i].v = rd();es[i].w = rd();

		if(i == id)val = es[i].w;

	}

	S = n + 1;T = S + 1;

	for(int i = 1;i <= m;++i)

	{

		if(i == id)

		{

			add(S,es[i].u,INF);

			add(es[i].v,T,INF);

		}

		else

		{

			add(es[i].u,es[i].v,max(0,val + 1 - es[i].w));

			add(es[i].v,es[i].u,max(0,val + 1 - es[i].w));

		}

	}

	cout << dinic() << endl;

	return 0;

}