unittest
{
	assert( [ "3 3 10", "1 2 20", "2 3 30", "1 3 45" ].parse.expand.solve == 35 );
	assert( [ "2 2 10", "1 2 100", "2 2 100" ].parse.expand.solve == -1 );
	assert( [ "4 5 10", "1 2 1", "1 4 1", "3 4 1", "2 2 100", "3 3 100" ].parse.expand.solve == 0 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nmp = input.front.split.to!( long[] );
	auto abcs = new long[ 3 ][ nmp[ 1 ] ];
	foreach( ref abc; abcs )
	{
		input.popFront;
		abc = input.front.split.to!( long[] );
		abc[ 0 .. 2 ] -= 1;
	}
	return tuple( nmp[ 0 ], nmp[ 2 ], abcs );
}

auto solve( long n, long p, long[ 3 ][] abcs )
{
	// 時間経過による支払いを経路のコストに含める
	// ついでに獲得コイン数をマイナスにして普通の最短経路問題にする
	foreach( ref abc; abcs )
	{
		abc[ 2 ] = p - abc[ 2 ];
	}
	
	// 最大獲得コイン数を計算
	auto cs = bellmanford( n, abcs, 0 );
	if( cs[ $ - 1 ] == long.min ) return -1L;							// 無限ループで最大値なし
	else                          return max( -cs[ $ - 1 ], 0L );		// 支払いより稼いでいれば獲得コイン数、そうでなければ0
}

// 正負の重み付きグラフの始点指定最短経路探索（ベルマンフォード法）
auto bellmanford( long n, long[ 3 ][] es, long s )
{
	auto ds = new long[ n ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	auto r = -1L;
	foreach( c; 0L .. n )
	{
		r = -1L;
		foreach( i, e; es )
		{
			if( ds[ e[ 0 ] ] == long.max || ds[ e[ 1 ] ] <= ds[ e[ 0 ] ] + e[ 2 ] ) continue;
			ds[ e[ 1 ] ] = ds[ e[ 0 ] ] + e[ 2 ];
			r = e[ 1 ];
		}
		if( r == -1 ) return ds;		// 更新がない場合、最短経路に収束済みなので打ち切り
	}
	
	// 頂点数-1回ループしても更新がある場合、負のループが存在する
	// 負のループ以降をminで塗りつぶす
	ds[ r ] = long.min;
	foreach( c; 0L .. n )
	{
		r = -1L;
		foreach( i, e; es )
		{
			if( ds[ e[ 0 ] ] != long.min || ds[ e[ 1 ] ] == long.min ) continue;
			ds[ e[ 1 ] ] = long.min;
			r = e[ 1 ];
		}
		if( r == -1 ) break;		// 更新がない場合、塗りつぶし済みなので打ち切り
	}
	return ds;
}
