#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
    {
        print("0: 0\n1:4\n:2:2");
    }
   
}