unittest
{
	assert( [ "3 2 1", "1 2 1 2", "1 3 2 4", "1 11", "1 2", "2 5" ].parse.expand.solve == "2\n14" );
	assert( [ "4 4 1", "1 2 1 5", "1 3 4 4", "2 4 2 2", "3 4 1 1", "3 1", "3 1", "5 2", "6 4" ].parse.expand.solve == "5\n5\n7" );
	assert( [ "6 5 1", "1 2 1 1", "1 3 2 1", "2 4 5 1", "3 5 11 1", "1 6 50 1", "1 10000", "1 3000", "1 700", "1 100", "1 1", "100 1" ].parse.expand.solve == "1\n9003\n14606\n16510\n16576" );
	assert( [ "4 6 1000000000", "1 2 50 1", "1 3 50 5", "1 4 50 7", "2 3 50 2", "2 4 50 4", "3 4 50 3", "10 2", "4 4", "5 5", "7 7" ].parse.expand.solve == "1\n3\n5" );
	assert( [ "2 1 0", "1 2 1 1", "1 1000000000", "1 1" ].parse.expand.solve == "1000000001" );
}



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 nms = input.front.split.to!( long[] );
	auto uvabs = new long[ 4 ][ nms[ 1 ] ];
	foreach( ref uvab; uvabs )
	{
		input.popFront;
		uvab = input.front.split.to!( long[] );
		uvab[ 0 .. 2 ] -= 1;
	}
	auto cds = new long[ 2 ][ nms[ 0 ] ];
	foreach( ref cd; cds )
	{
		input.popFront;
		cd = input.front.split.to!( long[] );
	}
	return tuple( nms[ 0 ], nms[ 2 ], uvabs, cds );
}

auto solve( long n, long s, long[ 4 ][] uvabs, long[ 2 ][] cds )
{
	auto nss = toAdjacencyListEx( n, uvabs, cds );
	auto anss = dijkstraEx( nss, uvabs.length + cds.length, 0, s );
	anss.popFront;
	return anss.to!( string[] ).join( "\n" );
}

// 辺配列から隣接リストを作成
auto toAdjacencyListEx( long n, long[ 4 ][] uvabs, long[ 2 ][] cds )
{
	auto nss = new Tuple!( long, long, long )[][ n ];
	foreach( uvab; uvabs )
	{
		nss[ uvab[ 0 ] ] ~= tuple( uvab[ 1 ], -uvab[ 2 ], uvab[ 3 ] );
		nss[ uvab[ 1 ] ] ~= tuple( uvab[ 0 ], -uvab[ 2 ], uvab[ 3 ] );
	}
	foreach( i, cd; cds )
	{
		nss[ i ] ~= tuple( i.signed, cd[ 0 ], cd[ 1 ] );
	}
	return nss;
}

// 正の重み付きグラフの始点指定最短経路探索（ダイクストラ法）
auto dijkstraEx( Tuple!( long, long, long )[][] nss, long ec, long s, long c )
{
	import std.container.binaryheap;
	
	auto am = nss.length.signed * 50;
	c = min( am, c );
	
	auto dss = new long[][]( nss.length, 1 + am );
	foreach( ref ds; dss ) ds[] = long.max;
	dss[ s ][ c ] = 0;
	auto dms = new long[ nss.length ];
	dms[] = long.max;
	dms[ s ] = 0;
	auto uss = new bool[][]( nss.length, 1 + am );
	
	auto queue = heapify!( ( a, b ) => b[ 2 ] < a[ 2 ] || ( b[ 2 ] == a[ 2 ] && b[ 1 ] < a[ 1 ] ) )( new Tuple!( long, long, long )[ ec ], 0 );
	queue.insert( tuple( s, c, 0L ) );
	while( !queue.empty )
	{
		auto fi = queue.front[ 0 ];
		auto fc = queue.front[ 1 ];
		auto fd = queue.front[ 2 ];
		queue.popFront();
		
		if( uss[ fi ][ fc ] ) continue;
		uss[ fi ][ fc ] = true;
		
		foreach( t; nss[ fi ] )
		{
			auto ti = t[ 0 ];
			auto tc = min( fc + t[ 1 ], am );
			auto td = fd + t[ 2 ];
			
			if( tc < 0 || uss[ ti ][ tc ] ) continue;
			
			dss[ ti ][ tc ] = td;
			dms[ ti ] = min( dms[ ti ], td );
			queue.insert( tuple( ti, tc, td ) );
		}
	}
	return dms;
}
