Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"math"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	dd := make([][]int, 1000)
	for i := range dd {
		dd[i] = make([]int, 1000)
	}
	num := make([]int,1000)
	inv := make([]int, 1001)
	x := make([]int, 1000)
	y := make([]int, 1000)
	vv := make([]int, 1000)
	nowt := make([]float64, 1000)
	rev := make([]int, 1000)
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf1 := strings.Split(scanner.Text(), " ")
			num[i], _ = strconv.Atoi(buf1[0])
			x[i], _ = strconv.Atoi(buf1[1])
			y[i], _ = strconv.Atoi(buf1[2])
			inv[num[i]] = i
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				dd[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
			}
		}
		scanner.Scan()
		m, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < m; i++ {
			scanner.Scan()
			buf2 := strings.Split(scanner.Text(), " ")
			c, _ := strconv.Atoi(buf2[0])
			d, _ := strconv.Atoi(buf2[1])
			c = inv[c]
			d = inv[d]
			for j := 0; j < n; j++ {
				vv[j] = 0
				nowt[j]=999999999
				rev[j]=-1
			}
			nowt[c]=0
			for j := 0; j < n; j++ {
				M := 99999999
				at := 0
				for k := 0; k < n; k++ {
					if vv[k] == 0 && float64(M) > nowt[k] {
						M=int(nowt[k])
						at = k
					}
				}
				if M > 90000000 {
					break
				}
				vv[at]=1
				for k := 0; k < n; k++ {
					if vv[k] == 0 && dd[at][k]<=2500&&nowt[k]>nowt[at]+math.Sqrt(float64(dd[at][k])) {
						nowt[k]=nowt[at]+math.Sqrt(float64(dd[at][k]))
						rev[k] = at
					}
				}
			}
			if vv[d] == 0 {
				fmt.Println("NA")
			} else {
				stack := make([]int, 0)
				V := d
				for V != c {
					stack = append(stack, V)
					V = rev[V]
				}
				fmt.Print(num[c])
				for len(stack) > 0 {
					fmt.Printf(" %d", num[stack[len(stack)-1]])
					stack = stack[:len(stack)-1]
				}
				fmt.Println()
			}
		}
	}
}

C++: using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    struct Point : IComparable
    {
        internal int to;
        internal double dist;
 
        public Point(int to, double dist)
        {
            this.to = to;
            this.dist = dist;
        }
 
        public int CompareTo(object obj)
        {
            Point other = (Point)obj;
 
            if (other.dist - dist > 0) return 1;    // rev
            if (other.dist == dist) return 0;
            return -1;
        }
    }
 
    struct State
    {
        internal double dist;
        internal string path;
    }
 
    class Problem
    {
        readonly int INF = 1 << 20;
        readonly int n;
 
        Dictionary<int, List<Point>> adj;
        State[][] memo;
        bool[] flg;
 
        public Problem(int n)
        {
            this.n = n;
            adj = new Dictionary<int, List<Point>>();
            memo = new State[n + 1][];
            flg = new bool[n + 1];
        }
 
        public void MakeMap()
        {
            var points = new Dictionary<int, KeyValuePair<int, int>>();
 
            for (int i = 0; i < n; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                int id = int.Parse(input[0]);
                int x = int.Parse(input[1]);
                int y = int.Parse(input[2]);
 
                points.Add(id, new KeyValuePair<int, int>(x, y));
                adj.Add(id, new List<Point>());
            }
 
            for (int i = 1; i <= n; i++)
            {
                for (int j = i + 1; j <= n; j++)
                {
                    int dx = points[i].Key - points[j].Key;
                    int dy = points[i].Value - points[j].Value;
                    double dist = Math.Sqrt(dx * dx + dy * dy);
 
                    if (dist > 50) continue;
 
                    adj[i].Add(new Point(j, dist));
                    adj[j].Add(new Point(i, dist));
                }
            }
        }
 
        public string GetPath(int s, int t)
        {
            if (!flg[s])
            {
                Dijkstra(s);
                flg[s] = true;
            }
 
            return memo[s][t].path == "" ? "NA" : memo[s][t].path;
        }
 
        private void Dijkstra(int s)
        {
            bool[] visited = new bool[n + 1];
 
            State temp;
            temp.dist = INF;
            temp.path = "";
 
            var d = Enumerable.Repeat(temp, n + 1).ToArray();
            d[s].dist = 0;
            d[s].path = s.ToString();
 
            PriorityQueue<Point> PQ = new PriorityQueue<Point>();
            PQ.Enqueue(new Point(s, 0));
 
            while (PQ.Count > 0)
            {
                Point f = PQ.Dequeue();
                int u = f.to;
                visited[u] = true;
 
                if (d[u].dist < f.dist) continue;
 
                for (int i = 0; i < adj[u].Count; i++)
                {
                    int v = adj[u][i].to;
 
                    if (visited[v]) continue;
 
                    double sumDist = d[u].dist + adj[u][i].dist;
 
                    if (d[v].dist > sumDist)
                    {
                        d[v].dist = sumDist;
                        d[v].path = d[u].path + " " + v;
 
                        PQ.Enqueue(new Point(v, d[v].dist));
                    }
                }
            }
            memo[s] = (State[])d.Clone();
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
 
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
 
                if (n == 0) break;
 
                Problem pb = new Problem(n);
                pb.MakeMap();
 
                int m = int.Parse(Console.ReadLine());
 
                while (m-- > 0)
                {
                    string[] input = Console.ReadLine().Split(' ');
                    int s = int.Parse(input[0]);
                    int t = int.Parse(input[1]);
 
                    sb.AppendLine(pb.GetPath(s, t));
                }
            }
            Console.Write(sb);
        }
    }
 
    class PriorityQueue<T> where T : IComparable
    {
        List<T> heap;
        int size;
 
        public PriorityQueue()
        {
            heap = new List<T>();
        }
 
        public int Count { get { return size; } }
 
        public void Enqueue(T x)
        {
            heap.Add(x);
            int i = size++;
 
            while (i > 0)
            {
                int p = (i - 1) / 2;
 
                if (Compare(heap[p], x) <= 0) break;
 
                heap[i] = heap[p];
                i = p;
            }
            heap[i] = x;
        }
 
        public T Dequeue()
        {
            T ret = heap[0];
            T x = heap[--size];
 
            int i = 0;
            while (i * 2 + 1 < size)
            {
                int a = i * 2 + 1;
                int b = i * 2 + 2;
 
                if (b < size && Compare(heap[b], heap[a]) < 0)
                    a = b;
                if (Compare(heap[a], x) >= 0)
                    break;
 
                heap[i] = heap[a];
                i = a;
            }
            heap[i] = x;
            heap.RemoveAt(size);
            return ret;
        }
 
        private int Compare(T x, T y)
        {
            return y.CompareTo(x);
        }
    }
}