Kちゃんの農場

KちゃんはMCの中にたくさんの農場を建てて、全部でn個で、農場ごとに作物を栽培する具体的な数を忘れてしまった.彼はあいまいな情報(全部でm個)しか覚えていない.以下の3つの形式で説明した.
農場aは農場bより少なくともc単位の作物を多く栽培し、農場aは農場bからc単位の作物を多く栽培し、農場aは農場bが栽培した作物の数と同じである.しかし、Kちゃんの記憶が少しずれているので、農場の栽培作物の数が彼の記憶のすべての情報と一致するように、存在するかどうかを知りたいと思っています.
入力フォーマットの第1行は、農場数とK記憶中の情報数をそれぞれ表す2つの整数nおよびmを含む.
次のm行:
各行の最初の数が1であれば、次いで3つの整数a,b,cがあり、農場aが農場bより少なくともc単位の作物を栽培していることを示す.
各行の最初の数が2であれば、次いで3つの整数a,b,cがあり、農場aが農場bからc単位の作物を多く栽培していることを示している.各行の最初の数が3であれば、次いで2つの整数a,bがあり、農場aの栽培数がbと同じくらい多いことを示している.
出力フォーマットがKちゃんの記憶と一致する場合は「Yes」、そうでない場合は「No」を出力します.
入出力サンプル入力#13 3 3 1 2 1 1 3 2 2 2 2 2
出力#1 Yes
説明/ヒント100%のデータ保証:1≦n,m,a,b,c≦10000.
. . . . . 差分制約を解析してdfsでspfaをシミュレートする
. . . . . . プログラム:

#include
#include
#include
using namespace std;

int head[100000],cnt=0,dis[20000];
bool f[100000];

struct edge
{
	int to,from,w;
} t[100000];

void add(int x,int y,int z)
{
	t[++cnt].to=y;t[cnt].from=head[x];t[cnt].w=z;head[x]=cnt;
}

bool spfa(int x)
{
	f[x]=true;
	for (int i=head[x];i;i=t[i].from)
	{
		int u=t[i].to;
		if (dis[x]+t[i].w>dis[u])
		{
			dis[u]=dis[x]+t[i].w;
			if (f[u]==true) return false;
			if (spfa(u)==false) return false;
		}
	}
	f[x]=false;
    return true;
}

int main()
{
	int n,m; 
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		int w,a,b,c;
		scanf("%d",&w);
		if (w==1)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(b,a,c);
		} else
		if (w==2)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,-c);
		} else
		if (w==3)
		{
			scanf("%d%d",&a,&b);
			add(a,b,0);
			add(b,a,0);
		}
	}
	
	for (int i=1;i<=n;i++)
	{
		add(0,i,0);
		dis[i]=-2147483647;
	}
	if (spfa(0)==false) printf("No"); else printf("Yes");
	return 0;
}