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 )
{
	// ゴールに到達できない辺を削除
	auto rs = dfs( n, abcs, 0, n - 1 );
	for( auto i = abcs.length.signed - 1; 0 <= i; i-- )
	{
		if( rs[ abcs[ i ][ 0 ] ] && rs[ abcs[ i ][ 1 ] ] ) continue;
		abcs = abcs[ 0 .. i ] ~ abcs[ i + 1 .. $ ];
	}
	
	// 時間経過による支払いを経路のコストに含める
	// ついでに獲得コイン数をマイナスにして普通の最短経路問題にする
	foreach( ref abc; abcs )
	{
		abc[ 2 ] = p - abc[ 2 ];
	}
	
	// 獲得コイン数の最大を計算
	auto cs = bellmanford( n, abcs, 0 );
	if( cs == null ) return -1;							// 無限ループで最大値なし
	else             return max( -cs[ $ - 1 ], 0 );		// 支払いより稼いでいれば獲得コイン数、そうでなければ0
}

// グラフの始点終点間経路探索（深さ優先探索）
auto dfs( long n, long[ 3 ][] es, long s, long g )
{
	auto rs = new bool[ n ];
	rs[ g ] = true;
	
	auto ds = new long[ n ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	auto nss = new long[][ n ];
	foreach( e; es )
	{
		nss[ e[ 0 ] ] ~= e[ 1 ];
	}
	
	bool[] f( ref bool[] rs, ref long[] ds, long[][] nss, long s, long g )
	{
		foreach( t; nss[ s ] )
		{
			if( ds[ s ] + 1 < ds[ t ] )
			{
				ds[ t ] = ds[ s ] + 1;
				f( rs, ds, nss, t, g );
			}
			if( rs[ t ] ) rs[ s ] = true;
		}
		return rs;
	}
	
	return f( rs, ds, nss, s, g );
}

// 正負の重み付きグラフの始点指定最短経路探索（ベルマンフォード法）
auto bellmanford( long n, long[ 3 ][] es, long s )
{
	import std.container.dlist;
	
	auto ds = new long[ n ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	foreach( c; 0L .. n )
	{
		auto r = false;
		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 = true;
		}
		if( !r ) return ds;		// 更新がない場合、最短経路に収束済みなので打ち切り
	}
	return null;		// 頂点数-1回ループしても更新がある場合、負のループが存在する
}
