template <typename T>

vector <T> dijkstra(const graph<T> &g, int start) {

  assert(0 <= start && start < g.n);

  vector<T> dist(g.n, numeric_limits<T>::max());

  dist[start] = 0;

  set< pair<T, int> > s;

  s.emplace(dist[start], start);

  while (!s.empty()) {

    int i = s.begin()->second;

    s.erase(s.begin());

    for (int id : g.g[i]) {

      if (g.ignore != nullptr && g.ignore(id)) {

        continue;

      }

      auto &e = g.edges[id];

      int to = e.from ^ e.to ^ i;

      if (dist[i] + e.cost < dist[to]) {

        s.erase({dist[to], to});

        dist[to] = dist[i] + e.cost;

        s.emplace(dist[to], to);

      }

    }

  }

  return dist;

  // returns numeric_limits<T>::max() if there's no path

}