背景

裸裸的“原题”啊^_^

描述

Pear养了n只小兔子,小兔子之间的关系由一种神奇的东西——“键”来决定。每个键有一个频率,称为键频率,键频率是一个整数。

被键连在一起的一群小兔子,我们称之为一个“家族”,小兔子A和B属于同一个家族当且仅当A和B之间有直接或间接的键连接。

例如,有四只小兔子A,B,C,D。如果AB,BC,BD之间都有键直接连接,那么小兔子A,B,C,D是一个家族。

Pear对不同的家族有不同的喜好程度,比如他很喜欢恰好包含3只小兔子的家族(幸福的三口之家),不喜欢只有1只小兔子的家族(谁会喜欢单身)。因此,他希望只保留某一段频率的键,比如10Hz~30Hz的键,此时频段宽度(频率最大值-频率最小值)=20Hz。Pear希望在保证它对所有的小兔子家族的喜好程度大于等于k的情况下,频段宽度尽可能的小,但至少要保留一个键(所有的键不能全都断开)。请求出最小的频段宽度。

输入格式

第一行有3个整数,n(小兔子的数量),m(键的数量),k

第二行有n个整数,第i个整数表示Pear对大小为i的小兔子家族的喜爱程度

接下来m行,每行有3个整数,u,v,f,表示小兔子u与小兔子v之间存在键,键频率为f Hz

输出格式

一行,最小的频段宽度(如果不存在可行频段,则输出“T_T”,不含引号)

样例输入

【样例输入1】

4 4 52

1 50 2 9

1 2 6

2 3 8

3 4 4

1 4 3 

【样例输入2】

4 4 10

1 5 2 9

1 2 6

2 3 8

3 4 4

1 4 3 

【样例输入3】

4 4 10

1 4 2 9

1 2 6

2 3 8

3 4 4

1 4 3 

样例输出

【样例输出1】

0

【样例输出2】

2

【样例输出3】

T_T

数据范围与约定

对于30%的数据,n\leq 10,m\leq 45

对于50%的数据,n\leq 50,m\leq 200

对于100%的数据,n\leq 1000,m\leq 5000

样例解释

【样例一】选择频段3Hz~3Hz或4Hz~4Hz或6Hz~6Hz或8Hz~8Hz

【样例二】选择频段4Hz~6Hz

【样例三】没有满足条件的频段

来源

NOI2011

每个测试点2s