// editor1
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
{
    struct edge;
    {
        int u,v,w;
    };
    struct graph{
        int n;
        struct edge*edges;
    };
    struct graph*creategraph(int n,int m)
    {
        struct graph*graph=(struct graph*)malloc(sizeof(struct graph));
        graph->n=n;
        graph->m=m;
        graph->edge=(struct edge*)malloc(m*sizeof(struct edge));
        return graph;
    }
    void bellmanford(struct graph*graph,int source);
    {
        int n=graph->n;
        int m=graph->m;
        long long dist;
        for(int i=0;i<n;i++)
        {
            dist[i]=LLONG_MAX;
        }
        dist[source]=0;
        for(int i=0;i<n;i++)
        {
            int u=graph->edge[j].u;
            int v=graph->edge[j].v;
            int w=graph->edge[j].w;
            if(dist[u]!=LLONG_MAX && dist[u]+w<dist[v])
            {
                dist[v]=dist[u]=w;
                
            }
        }
        for(int j=0;j<n;j++)
        {
            int u=graph->edge[j].u;
            int v=graph->edge[j].v;
            int w=graph->edge[j].w;
            if(dist[u]!=LLONG_MAX && dist[u]+w<dist[v])
            {
                printf("grah contains negative weight cycle\n");
                return;
            }
        }
           for(int i=0;i<n;i++) 
           {
               if(dist[u]!==LLONG_MAX)
               {
                   printf("%d:path not found\n",i);
                   else
                   {
                       printf("%d:%lld\n",i,dist[i]);
                   }
               }
               int main()
               {
                   int n,m,source;
                   if(scanf("%d"))
               }
           }
        }
    }
}