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 ds = transformEtoN_reverse( n, abcs ).bfs( n - 1 );
	for( auto i = abcs.length.signed - 1; 0 <= i; i-- )
	{
		if( ds[ abcs[ i ][ 0 ] ] < long.max && ds[ abcs[ i ][ 1 ] ] < long.max ) continue;
		abcs = abcs[ 0 .. i ] ~ abcs[ i + 1 .. $ ];
	}
	
	// 時間経過による支払いを経路のコストに含める
	foreach( ref abc; abcs )
	{
		abc[ 2 ] -= p;
	}
	
	// コイン数の最大を計算
	auto ts = transformEtoN!( true )( n, abcs ).bellmanford( abcs.length, 0 );
	if( ts == null ) return -1;							// 無限ループで最大値なし
	else             return max( ts[ $ - 1 ], 0 );		// 支払いより稼いでいればコイン数、そうでなければ0
}

// 辺配列を頂点配列に変換（辺の方向を逆にする）
auto transformEtoN_reverse( long nc, long[ 3 ][] es )
{
	auto nss = new long[][ nc ];
	foreach( e; es )
	{
		nss[ e[ 1 ] ] ~= e[ 0 ];
	}
	return nss;
}

// グラフの始点指定最短経路探索（幅優先探索）
auto bfs( long[][] nss, long s )
{
	import std.container.dlist;
	
	auto ds = new long[ nss.length ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	auto queue = make!DList( s );
	while( !queue.empty )
	{
		auto f = queue.front;
		queue.removeFront();
		
		foreach( t; nss[ f ] )
		{
			if( ds[ t ] < long.max ) continue;
			ds[ t ] = ds[ f ] + 1;
			queue.insertBack( t );
		}
	}
	return ds;
}

// 辺配列を頂点配列に変換
auto transformEtoN( bool directed = false )( long nc, long[ 3 ][] es )
{
	auto nss = new Tuple!( long, long )[][ nc ];
	foreach( e; es )
	{
		nss[ e[ 0 ] ] ~= tuple( e[ 1 ], e[ 2 ] );
		static if( !directed ) nss[ e[ 1 ] ] ~= tuple( e[ 0 ], e[ 2 ] );
	}
	return nss;
}

// 正負の重み付きグラフの始点指定最短経路探索（ベルマンフォード法）
auto bellmanford( Tuple!( long, long )[][] nss, long ec, long s )
{
	import std.container.binaryheap;
	
	auto ds = new long[ nss.length ];
	ds[] = long.min;
	ds[ s ] = 0;
	auto r = 0L;
	
	auto queue = heapify!( ( a, b ) => a[ 1 ] < b[ 1 ] )( new Tuple!( long, long )[ ec ], 0 );
	queue.insert( tuple( s, 0L ) );
	while( !queue.empty )
	{
		auto fi = queue.front[ 0 ];
		auto fd = queue.front[ 1 ];
		queue.popFront();
		
		if( fd < ds[ fi ] ) continue;
		
		foreach( t; nss[ fi ] )
		{
			auto ti = t[ 0 ];
			auto td = fd + t[ 1 ];
			
			if( td < ds[ ti ] ) continue;
			
			// 道（tdターン使用）
			ds[ ti ] = td;
			queue.insert( tuple( ti, td ) );
			r++;
			if( nss.length * 2 < r ) return null;
		}
	}
	return ds;
}
