# 幫 JC DEBUG

#include <iostream>
#include <vector>
//#include <algorithm>

using namespace std;
 
struct Edge
{
    int source;
    int destination;
    int weight;
};
 
struct Graph
{
    int V, E;
    struct Edge* edge;
};
 
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph)); // Vsize
    graph->V = V;  
    graph->E = E; 
    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) ); // E
    return graph;
}
 
void FinalSolution(int sauce, int dist[], int V)
{
    for (int i = 1; i < V+1; i++)
    {
        if(dist[i] > 99999999)
            cout<<"Shortest path from "<<sauce<<" to "<<i<<": No such path";
        else
            cout<<"Shortest path from "<<sauce<<" to "<<i<<": "<<dist[i];
            
        if(i != V)
            cout<<endl;
	}
}
 
void BellmanFord(struct Graph* graph, int source)
{
    int V = graph->V;
    int E = graph->E; 
    int StoreDistance[V+1];
 
    for (int i = 0; i < V+1; i++)
        StoreDistance[i] = 2147483000; // max
 
    StoreDistance[source] = 0;
 
    for (int i = 1; i <= V-1; i++)
    {
        // relax
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].source;
            int v = graph->edge[j].destination;
            int weight = graph->edge[j].weight;
            
            if (StoreDistance[u] + weight < StoreDistance[v])
                StoreDistance[v] = StoreDistance[u] + weight;
        }
    }
 
    // relax again
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].source;
        int v = graph->edge[i].destination; 
        int weight = graph->edge[i].weight;
 
        if (StoreDistance[u] + weight < StoreDistance[v])
        {
            cout<<"There is a negative cycle!";
            return;
        }
    }
 
    FinalSolution(source, StoreDistance, V);
 
    return;
}
 
int main()
{
    int vertexCount = 4;
    int edgeCount = 4;
    
    
    int source; 
    cin>>source;

    int tmp;
    vector<int> data;  
    vector<int> nodeId;
    for(int i = 0; /*i < edgeCount*3*/cin>>tmp; i++) 
    {
        data.push_back(tmp);
        
        // find new node?
        if(i % 3 != 2)
        {
            bool newNode = true;
            for(int j = 0; j < nodeId.size(); j++)
            {
               if(nodeId[j] == data[i])
               {
                   newNode = false;
               }
            }
            
            if(newNode)
            {
                nodeId.push_back(data[i]);
            }
        }
    }
    edgeCount = data.size()/3;
    vertexCount = nodeId.size();
    // cout<<nodeId.size();
    
    // create graph
    struct Graph* graph = createGraph(vertexCount, edgeCount);    
    for(int i=0; i < edgeCount ; i++)
    {
        graph->edge[i].source = data[i*3];
        graph->edge[i].destination = data[i*3+1];
        graph->edge[i].weight = data[i*3+2];
    }
    
    // TEST:
    // cout<<"==="<<endl;
    // cout<<vertexCount<<endl;
    // cout<<edgeCount<<endl;
    // for(int i = 0; i < edgeCount; i++)
    // {
    //     cout<<graph->edge[i].source<<" "<<graph->edge[i].destination<<" "<<graph->edge[i].weight<<endl;
    // }
    // cout<<"==="<<endl;
 
    BellmanFord(graph, source);


    return 0;
}