using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Grafos {
        public static class Djiskstra {
            /// <summary>
            /// https://j...content-available-to-author-only...d.com/pt/problems/view/1148
            /// </summary>
            public static void Test() {
                reset:
                string line = Console.ReadLine();
                int QtdCidades = int.Parse(line.Split(' ')[0]);
                int QtdLinhas  = int.Parse(line.Split(' ')[1]);
                if (QtdCidades == 0 && QtdLinhas == 0) { return; }

                Graph graph = new Graph(true);
                for (int i = 1; i <= QtdCidades; i++) {
                    graph.AddNode(i.ToString());
                }

                for (int i = 0; i < QtdLinhas; i++) {
                    line = Console.ReadLine();
                    string Cidade1 = line.Split(' ')[0];
                    string Cidade2 = line.Split(' ')[1];
                    int Value = int.Parse(line.Split(' ')[2]);
                    
                    Node Cid1 = graph.lstNodes.First(p => p.Data == Cidade1);
                    Node Cid2 = graph.lstNodes.First(p => p.Data == Cidade2);

                    List<Aresta> lstConnections = Cid2.lstConnections.Where(a => a.Destination == Cid1).ToList();
                    if (lstConnections.Count > 0) {
                        Value = 0;
                        foreach (var item in lstConnections) {
                            item.Value = 0;
                        }
                    }
                    graph.AddAresta(Cid1, Cid2, Value);
                }


                line = Console.ReadLine();
                if(line.Split(' ').Length > 2) { return; }
                int QtdConsultas = int.Parse(line.Trim());

                for (int i = 0; i < QtdConsultas; i++) {
                    line = Console.ReadLine();
                    string Cidade1 = line.Split(' ')[0];
                    string Cidade2 = line.Split(' ')[1];
                    Node mCidade1 = graph.lstNodes.First(p => p.Data == Cidade1);
                    Node mCidade2 = graph.lstNodes.First(p => p.Data == Cidade2);
                    int? Result = Run(graph, mCidade1, mCidade2);
                    Console.WriteLine(Result != null ? Result.ToString() : "Nao e possivel entregar a carta");
                }
                goto reset;
            }

            public static int? Run(Graph mGraph, Node Source, Node Target) {
                List<DjikstraObj> lstNodes = mGraph.lstNodes.Select(p => new DjikstraObj(p, null)).ToList();

                DjikstraObj mNodeCorrente = lstNodes.First(p => p.Node == Source);
                mNodeCorrente.Distance = 0;

                while (lstNodes.Any(p => !p.Visited)) {
                    List<DjikstraObj> lstNeighbors =
                        lstNodes.Where(p => !p.Visited).Where(n =>
                            //Destinos do nó corrente
                            mNodeCorrente.Node.lstConnections.Select(p => p.Destination)
                        .Contains(n.Node)).ToList(); 

                    foreach (DjikstraObj mNeighbor in lstNeighbors) {
                        int? TentativeDistance = mNodeCorrente.Distance + mNodeCorrente.Node.lstConnections.First(p => p.Destination == mNeighbor.Node).Value;
                        
                        // Update the neighbor's distance if the tentative distance is smaller
                        if (TentativeDistance != null && (mNeighbor.Distance == null || TentativeDistance < mNeighbor.Distance)) {
                            mNeighbor.Distance = TentativeDistance.Value;
                        }
                    }
                    
                    mNodeCorrente.Visited = true;
                    
                    // If there are no more unvisited nodes with distances, break out of the loop
                    if(lstNodes.Where(p => !p.Visited).All(p => p.Distance == null)) { 
                        break; 
                    }
                    
                    // Get the unvisited node with the smallest distance
                    mNodeCorrente = lstNodes.Where(p => !p.Visited && p.Distance != null)
                                        .OrderBy(p => p.Distance)
                                        .FirstOrDefault();
                                        
                    if(mNodeCorrente == null) { 
                        break; 
                    }
                }
                
                // Return the distance to the target node
                return lstNodes.First(p => p.Node == Target).Distance;
            }

            public class DjikstraObj {
                public Node Node { get; set; }
                public int? Distance { get; set; }
                public bool Visited { get; set; } = false;

                public DjikstraObj(Node Node, int? Distance) {
                    this.Node = Node;
                    this.Distance = Distance;
                }
            }
        }
    }

    namespace Grafos {
        // Node class representing vertices in the graph
        public class Node {
            public string Data { get; set; }
            public List<Aresta> lstConnections { get; set; } = new List<Aresta>();

            public Node(string Data = default(string)) {
                this.Data = Data;
            }

            public override string ToString() {
                return Data != null ?  $"{Data}" : "null";
            }
        }

        // Edge class representing connections between nodes
        public class Aresta {
            public int Value { get; set; }
            public Node Source { get; set; }
            public Node Destination { get; set; }

            public Aresta(Node source, Node destination, int Value = 0) {
                Source = source;
                Destination = destination;
                this.Value = Value;
            }

            public override string ToString() {
                return $"[{Value}, {Source} -> {Destination}]";
            }
        }

        // Graph class to manage nodes and connections
        public class Graph {
            public List<Node> lstNodes = new List<Node>();
            private bool isDirected = false;

            public Graph(bool directed = false) {
                isDirected = directed;
            }

            public List<Aresta> lstAresta {
                get {
                    return SelectMany(lstNodes, p => p.lstConnections).ToList();
                }
            }

        public static IEnumerable<TResult> SelectMany<TSource, TResult>(
        IEnumerable<TSource> source,
        Func<TSource, IEnumerable<TResult>> selector) {
                foreach (var item in source) {
                    foreach (var subItem in selector(item)) {
                        yield return subItem;
                    }
                }
            }


            // Add a node to the graph
            public Node AddNode(string data) {
                var node = new Node(data);
                lstNodes.Add(node);
                return node;
            }

            // Add an edge between two nodes
            public void AddAresta(Node source, Node destination, int Value = 0) {
                var edge = new Aresta(source, destination, Value);
                source.lstConnections.Add(edge);

                if (!isDirected) {
                    var reverseEdge = new Aresta(destination, source, Value);
                    destination.lstConnections.Add(reverseEdge);
                }
            }

            // Print the graph
            public void PrintGraph() {
                foreach (var node in lstNodes) {
                    Console.Write($"Node {node.Data}: ");
                    foreach (var edge in node.lstConnections) {
                        Console.Write($"({edge.Destination.Data}) ");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
    
namespace Grafos {
    public static class Program {
        static void Main(string[] args) {
            Djiskstra.Test();
        }
    }

}