#include <algorithm>
#include <assert.h>
#include <chrono>
#include <iostream>
#include <limits>
#include <random>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <unordered_set>
#include <set>
#include <list>
#include <functional>

template <class T>
class TimeMeasure {
public:
    TimeMeasure () {
        point_ = std::chrono::steady_clock::now();
    }
    int GetTime() {
        std::chrono::steady_clock::time_point current = std::chrono::steady_clock::now();
        int result = std::chrono::duration_cast<T>(current - point_).count();
        point_ = std::chrono::steady_clock::now();
        return result;
    }
    void SetLast() {
        point_ = std::chrono::steady_clock::now();
    }
private:
    std::chrono::steady_clock::time_point point_;
};

struct Querry {
    int from = -1;
    int to = -1;
};

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "{";
    for (const auto& item : vec) {
        os << item << " ";
    }
    os << "}";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& vec) {
    os << "{";
    for (const auto& item : vec) {
        os << item << " ";
    }
    os << "}";
    return os;
}

template<typename T, typename Q>
std::ostream& operator<<(std::ostream& os, const std::pair<T, Q>& item) {
    os << "[" << item.first << " " << item.second << "] ";
    return os;
}

std::vector<int> GenRandomArray(std::mt19937 *gen, int count, int from, int to) {
    std::uniform_int_distribution<int> dist(from, to);
    std::vector<int> data(count);
    for (auto& cur : data) {
        cur = dist(*gen);
    }
    return data;
}


struct Edge {
    int from = -1;
    int to = -1;
    int weight;
};

std::ostream& operator<<(std::ostream& stream, const Edge& edge) {
    stream << "[ " << edge.from << ", " << edge.to << ", " << edge.weight << "] ";
    return stream;
}

struct pair_hash
{
    template <class P, class Q>
    std::size_t operator() (const std::pair<P, Q> &pair) const
    {
        return std::hash<P>()(pair.first) ^ std::hash<Q>()(pair.second);
    }
};

std::vector<Edge> GenerateRandomGraph(std::mt19937 *gen,
                                      size_t graph_size,
                                      size_t edges_number, bool random_weight = false) {
    std::uniform_int_distribution<int> dist(0, graph_size - 1);
    std::uniform_int_distribution<int> dist_weight(0, 2);

    std::unordered_set<std::pair<int, int>, pair_hash> edges;
    std::vector<Edge> result;
    while (result.size() < edges_number) {
        auto pair = std::make_pair(dist(*gen), dist(*gen));
        if (pair.first == pair.second) {
            continue;
        }
        //        auto pair_second = std::make_pair(pair.second, pair.first);
        //        if (edges.count(pair) == 0 && edges.count(pair_second) == 0) {
        edges.insert(pair);

        result.push_back({pair.first + 1, pair.second + 1, 1000});
        if (random_weight) {
            result.back().weight = dist_weight(*gen);
        }
        //        }
    }
    return result;
}

std::vector<Edge> GenerateCycleGraph(std::mt19937 *gen,
                                     size_t graph_size, int number_of_cycles, int cycle_length,
                                     bool positive, std::unordered_set<int>& used_vertexes) {
    if (number_of_cycles * cycle_length + used_vertexes.size() > graph_size) {
        throw std::domain_error("WRONG PARAMS");
    }
    std::uniform_int_distribution<int> dist(0, graph_size - 1);

    std::vector<Edge> result;
    for (int cycle_num = 1; cycle_num <= number_of_cycles; ++cycle_num) {
        int starting_vertex;

        auto vert = dist(*gen);
        while (used_vertexes.count(vert) == 1) {
            vert = dist(*gen);
        }

        starting_vertex = vert;

        int last_vertex = starting_vertex;
        used_vertexes.insert(last_vertex);

        for (int index = 1; index < cycle_length; ++index) {
            auto vert = dist(*gen);
            while (used_vertexes.count(vert) == 1) {
                vert = dist(*gen);
            }

            result.push_back({last_vertex + 1, vert + 1, 1});
            last_vertex = vert;
            used_vertexes.insert(last_vertex);
        }

        if (positive) {
            result.push_back({last_vertex + 1, starting_vertex + 1, 1});
        } else {
            result.push_back({last_vertex + 1, starting_vertex + 1, -cycle_length});
        }
    }
    return result;
}

void Floyd(int vertex_number, const std::vector<Edge>& edges,
           std::vector<std::vector<int>>& distances) {

    for (const auto& edge: edges) {
        distances.at(edge.from - 1).at(edge.to - 1) =
                std::min(distances.at(edge.from - 1).at(edge.to - 1), edge.weight);
    }
    for (int i = 0; i < vertex_number; ++i) {
        distances.at(i).at(i) = 0;
    }

    for (int index_k = 0; index_k < vertex_number; ++index_k) {
        for (int index_i = 0; index_i < vertex_number; ++index_i) {
            for (int index_j = 0; index_j < vertex_number; ++index_j) {
                if (distances.at(index_i).at(index_k) == std::numeric_limits<int>::max()) {
                    continue;
                }
                if (distances.at(index_k).at(index_j) == std::numeric_limits<int>::max()) {
                    continue;
                }
                auto sum = distances.at(index_i).at(index_k) +
                        distances.at(index_k).at(index_j);
                if (distances.at(index_i).at(index_j) > sum) {
                    distances.at(index_i).at(index_j) = sum;
                }
            }
        }
    }
}

int BellmanFord(int vertex_number, std::vector<Edge>& edges) {
    //    std::cout<<edges<<std::endl;
    std::vector<int> distance(vertex_number + 1, std::numeric_limits<int>::max());
    std::vector<int> parent(vertex_number + 1, -1);
    for (int i = 1; i <=vertex_number; ++i) {
        edges.push_back({vertex_number + 1, i, 1});
    }
    //    std::cout<<edges<<std::endl;


    distance.at(vertex_number) = 0;

    for (int index = 0; index < vertex_number; ++index) {

        for (const auto& edge : edges) {
            if (distance.at(edge.from - 1) == std::numeric_limits<int>::max()) {
                continue;
            }
            if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
                distance.at(edge.to - 1) = distance.at(edge.from - 1) + edge.weight;
                parent.at(edge.to - 1) = edge.from - 1;
            }
        }
    }

    std::unordered_set<int> problem_vertex;
    for (const auto& edge : edges) {
        if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
            problem_vertex.insert(edge.from - 1);
            //            std::cout << " NEGATIVE LOOP " << std::endl;
        }
    }

    //    std::cout<<":LK:LK  "<<std::endl;
    int result = std::numeric_limits<int>::max();
    for (auto id : problem_vertex) {
        //        std::cout<<edges<<std::endl;
        //        std::cout<<problem_vertex<<std::endl;
        //        std::cout<<parent<<std::endl;
        {
            std::unordered_set<int> path;
            auto current = id;
            path.insert(current);
            while (parent.at(current) != vertex_number && parent.at(current) != -1 &&
                   path.count(parent.at(current)) == 0) {
                current = parent.at(current);
                //                std::cout << "K:ffLK: "<< current<<std::endl;
                path.insert(current);
            }
            //            std::cout<<":LK "<<std::endl;
            id = current;
            //            id = parent.at(current);
        }
        auto current = id;
        if (current == -1) {
            //            continue;
        }
        //        std::cout<<":LK:L  "<< current <<std::endl;
        //        std::vector<int> path;
        //        path.push_back(current);

        if (current < result) {
            result = current;
        }
        while (id != parent.at(current) && current != parent.at(current) &&
               -1 != parent.at(current)) {
            //            std::cout<<id<<" "<<current<<" "<<parent.at(current)<<std::endl;
            current = parent.at(current);
            //            path.push_back(current);
            if (current < result) {
                result = current;
            }
        }
        //        std::cout<<path<<std::endl;
    }
    //    std::cout << result << std::endl;
    //    std::cout<<problem_vertex<<std::endl;

    //    std::cout<<":LK:LK 2  "<<std::endl;

    if (result == std::numeric_limits<int>::max()) {
        return -1;
    }
    return result + 1;
}

std::vector<int> SolveSimple(int vertex_number, const std::vector<Edge>& edges,
                             const std::vector<Querry>& querries) {
    std::vector<std::vector<int>> distances(vertex_number,
                                            std::vector<int>(vertex_number,
                                                             std::numeric_limits<int>::max()));
    Floyd(vertex_number, edges, distances);

    std::vector<int> result(querries.size());
    for (size_t i = 0; i < querries.size(); ++i) {
        result[i] = distances.at(querries.at(i).from - 1).at(querries.at(i).to - 1);
        if (result[i] == std::numeric_limits<int>::max()) {
            result[i] = -1;
        }
    }
    return result;
}

class Graph {
public:
    explicit Graph(int vertex_number) : vertex_number_(vertex_number),
                               edges_(vertex_number) {
    }

    void AddEdge(int from, int to, int weight) {
        edges_[from].push_back(std::make_pair(to, weight));
    }

    std::vector<int> Dijkstra(int src, const std::vector<Querry>& querries,
                                         const std::vector<int>& querry_ind) {
        std::priority_queue<std::pair<int, int>,
                std::vector<std::pair<int, int>>,
                std::greater<std::pair<int, int>>> heap;
        std::vector<int> distances(vertex_number_, std::numeric_limits<int>::max());

        heap.push(std::make_pair(0, src));
        distances[src] = 0;
        std::unordered_set<int> to_set;
        for (const auto& ind : querry_ind) {
            to_set.insert(querries.at(ind).to - 1);
        }

        while (!heap.empty())
        {
            int u_vertex = heap.top().second;
            to_set.erase(u_vertex);
            heap.pop();
            if (to_set.empty()) {
                break;
            }

            for (auto it = edges_[u_vertex].begin(); it != edges_[u_vertex].end(); ++it) {
                auto dist = distances[u_vertex] + it->second;
                if (distances[it->first] > dist)
                {
                    distances[it->first] = dist;
                    heap.push(std::make_pair(distances[it->first], it->first));
                }
            }
        }

        return distances;
    }

private:
    int vertex_number_;
    std::vector<std::vector<std::pair<int, int>>> edges_;
};

template <class T>
class Heap {
public:
    explicit Heap(bool min_or_max) : min_or_max_(min_or_max) {
    }

    void Add(const T& value) {
        auto position = values_.size();
        values_.push_back(value);
        auto current_position = SiftUpStep(position);
        while (position != current_position) {
            position = current_position;
            current_position = SiftUpStep(current_position);
        }
    }

    T ExtractMin() {
        auto result = values_.at(0);
        DeleteByPosition(0);
        return result;
    }

    const T& GetTop() const {
        assert(!values_.empty());
        return values_.front();
    }

    bool Empty() const {
        return values_.empty();
    }

    size_t GetSize() const {
        return values_.size();
    }

    void DecreasePriority(const T& item) {
        bool found = false;
        for (size_t ind = 0; ind < values_.size(); ++ind) {
            if (values_[ind].key == item.key) {
                values_[ind].priority = item.priority;
                auto position = ind;
                auto current_position = SiftUpStep(position);
                while (position != current_position) {
                    position = current_position;
                    current_position = SiftUpStep(current_position);
                }
                found = true;
                break;
            }
        }

        if (!found) {
            Add(item);
        }
    }

    const auto& GetValues() const {
        return values_;
    }

private:
    bool min_or_max_;
    const size_t heap_arity_ = 2;
    std::vector<T> values_;
    std::vector<T> deleted_values_;

    inline bool compare_(const T& lhs, const T& rhs) const {
        if (min_or_max_) {
            return lhs.priority > rhs.priority;
        } else {
            return lhs.priority < rhs.priority;
        }
    }

    void DeleteByPosition(size_t position) {
        if (position + 1 == values_.size()) {
            values_.pop_back();
            return;
        }
        values_.at(position) = values_.back();
        values_.pop_back();

        auto current_position = SiftUpStep(position);
        while (position != current_position) {
            position = current_position;
            current_position = SiftUpStep(current_position);
        }

        current_position = SiftDownStep(position);
        while (position != SiftDownStep(position)) {
            position = current_position;
            current_position = SiftDownStep(current_position);
        }
    }

    size_t SiftUpStep(size_t position) {
        if (position == 0) {
            return position;
        } else {
            auto parent = GetParent(position);
            if (compare_(values_.at(position), values_.at(parent))) {
                std::swap(values_.at(position), values_.at(parent));
                return parent;
            } else {
                return position;
            }
        }
    }

    size_t SiftDownStep(size_t position) {
        auto child = GetBestChild(position);
        if (child != std::numeric_limits<size_t>::max()) {
            if (compare_(values_.at(child), values_.at(position))) {
                std::swap(values_.at(child), values_.at(position));
            }
            return child;
        } else {
            return position;
        }
    }

    size_t GetBestChild(size_t position) const {
        size_t result = std::numeric_limits<size_t>::max();
        for (size_t i = 0; i < heap_arity_; ++i) {
            auto child_ind = GetKthChild(position, i);
            if (child_ind < values_.size()) {
                if (i == 0) {
                    result = child_ind;
                } else {
                    if (compare_(values_.at(child_ind), values_.at(result))) {
                        result = child_ind;
                    }
                }
            }
        }
        return result;
    }
    size_t GetParent(size_t ind) const {
        return (ind - 1) / heap_arity_;
    }

    size_t GetKthChild(size_t ind, size_t k_num) const {
        assert(k_num < heap_arity_);
        return  heap_arity_ * ind + k_num + 1;
    }
};

struct HeapItem {
    int key = -1;
    int priority = -1;
};

template <class T>
std::ostream& operator<<(std::ostream& os, const Heap<T>& heap) {
    for (const auto& item : heap.GetValues()) {
        os << item << " | ";
    }
    return os;
}

std::ostream& operator<<(std::ostream& os, const HeapItem& item) {
    os << "[" << item.key << ", " << item.priority << "]";
    return os;
}

bool operator==(const HeapItem& lhs, const HeapItem& rhs) {
    return lhs.key == rhs.key && lhs.priority == rhs.priority;
}

class PriorityQueue {
public:
    void AddItem (const HeapItem& item) {
        //        std::cout<<":LK:dfdL  "<<item.key<<" "<<item.priority<<std::endl;

        values_.push_back(item);
    }

    HeapItem ExtractMin() {
        assert(!values_.empty());
        //        std::cout<<"VALS "<<values_<<std::endl;
        int lowest_proirity = values_.front().priority;
        HeapItem result = values_.front();
        for (const auto& item : values_) {
            if (item.priority < lowest_proirity) {
                lowest_proirity = item.priority;
                result = item;
            }
        }
        //        assert(lowest_proirity != std::numeric_limits<int>::max());
        //        std::cout<<":LK:L  "<<result.key<<" "<<result.priority<<std::endl;
        //        std::cout<<"LKL "<<values_.size()<<std::endl;
        auto it = std::find(values_.begin(), values_.end(), result);
        assert(it != values_.end());

        //        std::cout<<":LK:L  "<<it - values_.begin()<<std::endl;
        values_.erase(it);
        //        std::cout<<"LKL0 "<<values_.size()<<std::endl;

        return result;
    }

    void DecreasePriority(const HeapItem& item) {
        for (auto& val : values_) {
            if (item.key == val.key) {
                val.priority = item.priority;
            }
        }
    }

    bool Empty() const {
        return values_.empty();
    }

private:
    std::vector<HeapItem> values_;
};

std::vector<int> Dijkstra(int vertex_number, int source,
                          const std::vector<std::vector<Edge>>& edges) {
    //    std::cout<<":LK:LK :1"<<std::endl;
    //    PriorityQueue queue;
    Heap<HeapItem> heap(false);
    std::vector<int> distances(vertex_number, std::numeric_limits<int>::max());
    distances.at(source) = 0;

    heap.Add({source, 0});
    for (int i = 0; i < vertex_number; ++i) {
        //        queue.AddItem({i, distances.at(i)});
        //        heap.Add({i, distances.at(i)});
    }
    //    std::cout<<":LK:LK :10"<<std::endl;

    std::unordered_set<int> all_vertices;
    while (!heap.Empty()) {
        auto item = heap.ExtractMin();
        for (const auto& neighbor : edges.at(item.key)) {
            if (item.priority == std::numeric_limits<int>::max()) {
                continue;
            }
            int current_dist = item.priority + neighbor.weight;
            if (current_dist < distances.at(neighbor.to - 1)) {
                distances.at(neighbor.to - 1) = current_dist;
                heap.DecreasePriority({neighbor.to - 1, current_dist});
            }
        }
    }
    return distances;
}

std::vector<int> Solve(int vertex_number, const std::vector<Edge>& edges,
                       const std::vector<Querry>& querries) {
    Graph graph(vertex_number);
    for (const auto& item : edges) {
        graph.AddEdge(item.from - 1, item.to - 1, item.weight);
    }
    std::vector<std::vector<int>> querries_sorted(vertex_number);
    for (size_t i = 0; i < querries.size(); ++i) {
        querries_sorted.at(querries.at(i).from - 1).push_back(i);
    }

    std::vector<int> result_second(querries.size());
    uint64_t total_time = 0;
    for (int i = 0; i < vertex_number; ++i) {
        auto row = graph.Dijkstra(i, querries, querries_sorted.at(i));
        for (const auto& ind : querries_sorted.at(i)) {
            if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
                result_second[ind] = -1;
            } else {
                result_second[ind] = row.at(querries.at(ind).to - 1);
            }
        }
    }
    total_time/=1000;
    //    std::cout<<":LK:LK:L  "<<total_time<<std::endl;
    return result_second;
}


std::vector<int> SolveThi(int vertex_number, const std::vector<Edge>& edges,
                          const std::vector<Querry>& querries) {

    std::vector<std::vector<Edge>> edges_sorted(vertex_number);
    for (const auto& item : edges) {
        edges_sorted.at(item.from - 1).push_back(item);
    }
    std::vector<std::vector<int>> querries_sorted(vertex_number);
    for (size_t i = 0; i < querries.size(); ++i) {
        querries_sorted.at(querries.at(i).from - 1).push_back(i);
    }

    std::vector<int> result_second(querries.size());
    uint64_t total_time = 0;
    for (int i = 0; i < vertex_number; ++i) {
        auto row = Dijkstra(vertex_number, i, edges_sorted);
        for (const auto& ind : querries_sorted.at(i)) {
            if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
                result_second[ind] = -1;
            } else {
                result_second[ind] = row.at(querries.at(ind).to - 1);
            }
        }
    }
    total_time/=1000;
    //    std::cout<<":LK:LK:L  "<<total_time<<std::endl;
    return result_second;
}

void StressTest() {
    {
        std::mt19937 generator(72874);

        for (size_t loop_index = 0; loop_index < 10000; ++loop_index) {
            //            std::cout<<loop_index<<std::endl;
            int vertex_number = 20;
            auto edges = GenerateRandomGraph(&generator, vertex_number,
                                             2 * vertex_number, true);
            int querry_size = 100;
            auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
            auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);

            std::vector<Querry> querries(querry_size);
            for (int i = 0; i < querry_size; ++i) {
                querries[i].from = from.at(i);
                querries[i].to = to.at(i);
            }

            auto result = Solve(vertex_number, edges, querries);
            auto true_result = SolveSimple(vertex_number, edges, querries);
            if (true_result != result) {
                throw std::runtime_error("Stress test failed");
            }
        }

        std::cout << "STRESS TEST OK" << std::endl;
    }
}

void SpeedTest() {
    {
        std::mt19937 generator(72874);

        for (size_t loop_index = 0; loop_index < 100; ++loop_index) {
            int vertex_number = 2000;
            auto edges = GenerateRandomGraph(&generator, vertex_number, 20000, true);
            int querry_size = 10000;
            auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
            auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);

            std::vector<Querry> querries(querry_size);
            for (int i = 0; i < querry_size; ++i) {
                querries[i].from = from.at(i);
                querries[i].to = to.at(i);
            }

            TimeMeasure<std::chrono::milliseconds> timer;
            Solve(vertex_number, edges, querries);

            std::cout << "TIME DIFF " << timer.GetTime() << std::endl;
        }
    }
}

void TestSolution() {
    {
        int vertex_number = 1;
        std::vector<Edge> edges;
        edges.push_back({1, 1, 1});
        std::vector<Querry> querry;
        querry.push_back({1, 1});
        auto result = Solve(vertex_number, edges, querry);
        std::vector<int> true_result;
        true_result.push_back(0);
        if (result != true_result) {
            throw std::runtime_error("TEST FAILED 1");
        }
    }

    {
        int vertex_number = 5;
        std::vector<Edge> edges;
        edges.push_back({1, 2, 2});
        edges.push_back({2, 3, 0});
        edges.push_back({2, 4, 2});
        edges.push_back({3, 4, 1});

        std::vector<Querry> querry;
        querry.push_back({1, 4});
        querry.push_back({2, 5});

        auto result = Solve(vertex_number, edges, querry);
        std::vector<int> true_result;
        true_result.push_back(3);
        true_result.push_back(-1);

        if (result != true_result) {
            throw std::runtime_error("TEST FAILED 2");
        }
    }

    std::cout << "TESTS OK " << std::endl;
}

int main() {
    TestSolution();
    StressTest();
    SpeedTest();
    return 0;
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int vertex_number;
    int edge_number;
    std::cin >> vertex_number >> edge_number;
    std::vector<Edge> edges(edge_number);
    for (auto& edge : edges) {
        std::cin >> edge.from >> edge.to >> edge.weight;
    }
    int querry_number;
    std::cin >> querry_number;
    std::vector<Querry> querries(querry_number);
    for (auto& item : querries) {
        std::cin >> item.from >> item.to;
    }
    auto result = Solve(vertex_number, edges, querries);
    for (const auto& item : result) {
        std::cout << item << "\n";
    }
}