#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int oo = 0x3f3f3f3f;

class Graph {
  public:
    class Edge {
      public:
        Edge(const int _from = NIL, const int _to = NIL, const int _cost = 0):
          from(_from),
          to(_to),
          cost(_cost) {}

        int From() const {
            return from;
        }

        int To() const {
            return to;
        }

        int Cost() const {
            return cost;
        }

      private:
        int from, to, cost;
    };

    static const int NIL = -1;

    Graph(const int _v = 0):
      v(_v),
      edges(vector< vector<Edge> >(_v, vector<Edge>())) {}

    int V() const {
        return v;
    }

    vector<Edge>::const_iterator EdgesBegin(const int x) const {
        return edges[x].begin();
    }

    vector<Edge>::const_iterator EdgesEnd(const int x) const {
        return edges[x].end();
    }

    void AddEdge(const Edge &e) {
        edges[e.From()].push_back(e);
    }

  private:
    int v;
    vector< vector<Edge> > edges;
};

Graph G;
vector<int> Distances;

void Dijkstra(const Graph &graph, const int source, vector<int> &distances) {
    distances = vector<int>(graph.V(), oo);
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;
    heap.push(make_pair(0, source));
    while (!heap.empty()) {
        int x = heap.top().second, c = heap.top().first;
        heap.pop();
        if (distances[x] != oo)
            continue;
        distances[x] = c;
        for (vector<Graph::Edge>::const_iterator e = graph.EdgesBegin(x); e != graph.EdgesEnd(x); ++e)
            if (distances[e->To()] == oo)
                heap.push(make_pair(c + e->Cost(), e->To()));
    }
}

void Solve() {
    Dijkstra(G, 0, Distances);
}

void Read() {
    ifstream cin("dijkstra.in");
    int v, e;
    cin >> v >> e;
    G = Graph(v);
    for (; e > 0; --e) {
        int from, to, cost;
        cin >> from >> to >> cost;
        G.AddEdge(Graph::Edge(--from, --to, cost));
    }
    cin.close();
}

void Print() {
    ofstream cout("dijkstra.out");
    for (int x = 1; x < G.V(); ++x) {
        if (Distances[x] == oo)
            Distances[x] = 0;
        cout << Distances[x] << " ";
    }
    cout << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}