1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<algorithm>

  5 #include<queue>

  6

  7 using namespace std;

  8

  9 const int MAXN=5010;

 10 const int MAXM=125100;

 11 const int MOD = 1e9+7;

 12 int n,m,k,cnt;

 13 int head[MAXN];

 14 int d[MAXN][60];

 15

 16 struct Edge{

 17     int s,t,w,next;

 18 }edge[MAXM<<1];

 19

 20 inline int read(){

 21     int s=0,w=1;

 22     char ch=getchar();

 23     while (ch<'0'||ch>'9'){

 24         if(ch == '-')     w  = -1;

 25             ch = getchar();

 26     }

 27     while (ch>='0'&&ch<='9'){

 28         s=s*10+ch-'0';

 29         ch=getchar();

 30     }

 31     return s*w  ;

 32 }

 33

 34 void Add(int u,int v ,int wi ){

 35     cnt++ ;

 36     edge[cnt].s=u;

 37     edge[cnt].t=v;

 38     edge[cnt].w=wi;

 39     edge[cnt].next = head[u];

 40     head[u] = cnt;

 41 }

 42

 43 struct HeapNode{

 44     int pos , dis , v ;

 45     bool operator < ( const HeapNode  &a ) const {

 46         return  a.dis < dis ;

 47     }

 48 };

 49

 50 void dijkstra( ){

 51     priority_queue<HeapNode>Q;

 52     for(int i = 1;i <= n;i++){

 53         for(int j = 0 ; j <= k; j++ ){

 54             d[i][j]=2147483647;

 55         }

 56     }

 57     d[1][0] = 0 ;

 58     Q.push((HeapNode){1,0,0});

 59     while(!Q.empty()){

 60         HeapNode tmp = Q.top() ;

 61         int u = tmp.pos;

 62         int t = tmp.v;

 63         if( d[u][t] != tmp.dis     ){

 64             Q.pop();

 65             continue;

 66         }

 67         Q.pop();

 68     for(int i  = head[u] ; i ; i = edge[i].next ){

 69         int to  = edge[i].t ;

 70         int wi =  edge[i].w ;

 71         if( d[to][t] > d[u][t] + wi  ){

 72             d[to][t] = d[u][t] + wi ;

 73             Q.push ( (HeapNode) {  to, d[to][t] , t  });

 74             }

 75              if( t<k &&d[to][t+1] >(d[u][t]) + (edge[i].w>>1)){

 76                d[to][t+1] = d[u][t] + (edge[i].w>>1);

 77                Q.push( (HeapNode){to , d[to][t+1], t+1 });

 78             }

 79          }

 80     }

 81 }

 82

 83 int main(){

 84

 85     n=read(); m=read();  k=read();

 86

 87     for(int i = 1 ;i <= m ; i++ ){

 88         int x , y , z ;

 89         x=read() ; y=read() ; z=read() ;

 90         Add(x,y,z);  Add(y,x,z);

 91     }

 92

 93     int time;

 94     time= read();

 95     int minn=2147483647;

 96

 97     dijkstra() ;

 98     for(int i=0;i<=k;i++){

 99         minn = min(minn , d[n][i]) ;

100     }

101

102     if(minn > time ){

103         printf("QaQ\n");

104     }

105     else printf("YES\n");

106     printf("%d",minn%MOD);

107     return 0;

108 }