#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#define COST first
#define DIS first
#define NODE second
#define TO second
#define INF 0x7fffffff

using namespace std;

typedef pair<int,int> edge;
bool vis[50001];

int main()
{
    vector< vector<edge> > graph(50001);
    priority_queue <edge, vector<edge>, greater<edge> > S;
    int dis[50001], n, m;

    ifstream in("dijkstra.in");
    in >> n >> m;

    for (;m;--m)
    {
        int a, b, c;
        in >> a >> b >> c;
        graph[a].push_back(make_pair(c,b));
    }
    in.close();
    for (int i = 2; i <= n; i++)
        dis[i] = INF;

    S.push(make_pair(0,1));

    while(!S.empty())
    {
        int d = S.top().DIS;
        int x = S.top().NODE;
        S.pop();
        if(vis[x])
            continue;
        vis[x] = true;
        for(int i = 0; i < graph[x].size(); ++i)
        {
            if(dis[graph[x][i].TO] > d + graph[x][i].COST)
            {
                dis[graph[x][i].TO] = d + graph[x][i].COST;
                S.push(make_pair(d + graph[x][i].COST, graph[x][i].TO));
            }
        }
    }

    ofstream out("dijkstra.out");
    for(int i = 2;i<=n;++i)
    {
        if(dis[i]!=INF)
            out << dis[i] << " ";
        else
            out << 0 << " ";
    }
    out.close();

    return 0;
}