class Solution
{
static Dictionary<int, List<Edge>> dict;
static int[] visited;
static int[] cost;
static string answer;
static void Main(string[] args)
{
    answer = "";
    int t = Convert.ToInt32(Console.ReadLine());
    for (int a0 = 0; a0 < t; a0++)
    {
    dict = new Dictionary<int, List<Edge>>();
    string[] tokens_n = Console.ReadLine().Split(' ');
    int n = Convert.ToInt32(tokens_n[0]);
    int m = Convert.ToInt32(tokens_n[1]);
    visited = Enumerable.Repeat(-1, n).ToArray();
    cost = Enumerable.Repeat(int.MaxValue, n).ToArray();
    for (int a1 = 0; a1 < m; a1++)
    {
        string[] tokens_x = Console.ReadLine().Split(' ');
        int x = Convert.ToInt32(tokens_x[0]);
        int y = Convert.ToInt32(tokens_x[1]);
        int r = Convert.ToInt32(tokens_x[2]);
        if (y < x)
        {
            int temp = x;
            x = y;
            y = temp;
        }

        if (dict.ContainsKey(x))
        {
            List<Edge> list = new List<Edge>();
            dict.TryGetValue(x, out list);
            Edge e = (from l in list where l.Dest == y select l).SingleOrDefault();
            if (e == null)
            {
                list.Add(new Edge(y, r));
            }
            else if (e.Cost > r)
            {
                e.Cost = r;
            }
        }
        else
        {
            List<Edge> list = new List<Edge>();
            list.Add(new Edge(y, r));
            dict.Add(x, list);
        }
        if (dict.ContainsKey(y))
        {
            List<Edge> list = new List<Edge>();
            dict.TryGetValue(y, out list);
            Edge e = (from l in list where l.Dest == x select l).SingleOrDefault();
            if (e == null)
            {
                list.Add(new Edge(x, r));
            }
            else if (e.Cost > r)
            {
                e.Cost = r;
            }
        }
        else
        {
            List<Edge> list = new List<Edge>();
            list.Add(new Edge(x, r));
            dict.Add(y, list);
        }
    }
    int s = Convert.ToInt32(Console.ReadLine());
    Dijkstra(s);
    foreach (int i in cost)
    {
        if (i == 0)
        {
            continue;
        }
        if (i == int.MaxValue)
        {
            answer += -1 + " ";
        }
        else
        {
            answer += i + " ";
        }
    }
    answer += "n";
}
Console.WriteLine(answer);
}

static void Dijkstra(int source)
{
    cost[source - 1] = 0;
    visited[source - 1] = 1;
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(source);
while (queue.Count != 0)
{
    int curr_source = queue.Dequeue();
    if (dict.ContainsKey(curr_source))
    {
        List<Edge> list = new List<Edge>();
        dict.TryGetValue(curr_source, out list);
        foreach (Edge e in list)
        {
            int alternate_cost = e.Cost + cost[curr_source - 1];
            if (alternate_cost < cost[e.Dest - 1])
            {
                cost[e.Dest - 1] = alternate_cost;
            }
            if (visited[e.Dest - 1] == -1)
            {
                visited[e.Dest - 1] = 1;
                queue.Enqueue(e.Dest);
            }
        }
      }
    }
  }
}

class Edge
{
    public Edge(int dest, int cost)
    {
        Dest = dest;
        Cost = cost;
     }

    public int Dest { get; set; }
    public int Cost { get; set; }
}