#include<stdio.h>
int main()
{
    int n,m;
    scanf("%d\n%d",&n,&m);
    int a[n],b[n],c[n];
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
    }
    int l;
    scanf("%d",&l);
    if(n<1)
    {
        printf("Invalid input");
    }
    else if(m<0)
    {
        for(int i=0;i<m;i++)
            printf("%d: Path not found",i);
    }
    else
    {
        for(int i=0;i<=i;i++)
        {
            printf("%d: %d",i,a[0]);
        }
    }
   
}