#include

using namespace std;

int main()

{

freopen("1.in","r",stdin);

freopen("1.out","w",stdout);

int n,m,s;

scanf("%d%d%d",&n,&m,&s);

int dist[n+1],path[m+1][3],i,j,u,v;

for(i=1;i