Примерно решение №2

using System;
using System.Collections.Generic;
using System.Linq;
using Wintellect.PowerCollections;

namespace _02.Third
{
    public class Edge
    {
        public int From { get; set; }
        public int To { get; set; }
        public int Time { get; set; }
        public override string ToString()
        {
            return $"{From} {To} {Time}";
        }

    }
    class Program
    {
        private static List<Edge>[] graph;
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var input = Console.ReadLine()
                .Split()
                .Select(int.Parse).ToArray();
              var exits=new HashSet<int>(input);
            int e = int.Parse(Console.ReadLine());
            graph = ReadGraph(n, e, exits);
            var limitArgs = Console.ReadLine();
            int limit = FormatTimeArgs(limitArgs);

            var bestDistance = Enumerable.Repeat(int.MaxValue, n).ToArray();
            foreach (var exit in exits)
            {
                for (int node = 0; node < graph.Length; node++)
                {
                    if (!exits.Contains(node))
                    {
                        var currDistance = GetDistance(node, exit);
                        if (currDistance < bestDistance[node])
                        {
                            bestDistance[node] = currDistance;
                        }
                    }
                }
            }
            for (int node = 0; node < graph.Length; node++)
            {
                if (!exits.Contains(node))
                {
                    var currTime = bestDistance[node];
                    if (currTime == int.MaxValue)
                    {
                        Console.WriteLine($"Unreachable {node} (N/A)");
                        continue;
                    }
                    var timeHour = (currTime / 3600);
                    var timeMinute = ((currTime - timeHour * 3600) / 60);
                    var timeSecond = (currTime - timeHour * 3600 - timeMinute * 60);

                    var timeAsString = $"{timeHour.ToString().PadLeft(2, '0')}:" +
                        $"{timeMinute.ToString().PadLeft(2, '0')}" +
                        $":{timeSecond.ToString().PadLeft(2, '0')}";
                    if (currTime > limit)
                    {
                        Console.WriteLine($"Unsafe {node} ({timeAsString})");
                    }
                    else
                    {
                        Console.WriteLine($"Safe {node} ({timeAsString})");
                    }
                }
            }
        }

        private static int GetDistance(int startNode, int exit)
        {
            var distance = Enumerable.Repeat(int.MaxValue, graph.Length).ToArray();
            distance[startNode] = 0;
            var visited = new bool[graph.Length];
            visited[startNode] = true;
            var queue = new OrderedBag<int>
                (Comparer<int>.Create
                ((f, s) => distance[f] - distance[s]));
            queue.Add(startNode);
            while (queue.Count > 0)
            {
                var node = queue.RemoveFirst();
                if (node == exit)
                {
                    return distance[node];
                }

                foreach (var child in graph[node])
                {
                    var childNode = node == child.From
                        ? child.To
                        : child.From;
                    if (distance[childNode] == int.MaxValue)
                    {
                        queue.Add(childNode);
                    }
                    var currDistance = child.Time + distance[node];
                    if (currDistance < distance[childNode])
                    {
                        distance[childNode] = currDistance;
                        queue = new OrderedBag<int>
                            (queue, Comparer<int>.Create
                            ((f, s) => distance[f] - distance[s]));
                    }
                }
            }
            return int.MaxValue;
        }

        private static List<Edge>[] ReadGraph(int n, int e, HashSet<int> exits)
        {
            var result = new List<Edge>[n];
            for (int i = 0; i < n; i++)
            {
                result[i] = new List<Edge>();
            }
            for (int i = 0; i < e; i++)
            {
                var tokens = Console.ReadLine()
                    .Split();
                int from = int.Parse(tokens[0]);
                int to = int.Parse(tokens[1]);

                int time = FormatTimeArgs(tokens[2]);
                var edge = new Edge
                {
                    From = from,
                    To = to,
                    Time = time
                };
                result[from].Add(edge);
                if (!exits.Contains(to))
                {
                    result[to].Add(edge);
                }
            }
            return result;
        }

        private static int FormatTimeArgs(string timeData)
        {
            int time = 0;
            var timeArgs = timeData
                    .Split(new[] { ":" }, StringSplitOptions.RemoveEmptyEntries);
            if (timeArgs[0][0] == '0')
            {
                time += int.Parse(timeArgs[0][1].ToString()) * 60;
            }
            else
            {
                time += int.Parse(timeArgs[0]) * 60;
            }
            if (timeArgs[1][0] == '0')
            {
                time += int.Parse(timeArgs[1][1].ToString());
            }
            else
            {
                time += int.Parse(timeArgs[1]);
            }

            return time;
        }
    }
}