#include <bits/stdc++.h>
#define nmax 100002
#define infinity 1200000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, p;
int cost_of_distance[nmax], sols[nmax];
bool checked[nmax];
struct dublu{
    int dest, cost;
};

struct comp{
    bool operator()(int x, int y)
    {
        return cost_of_distance[x]  > cost_of_distance[y];
    }
};
vector<dublu> graphs[nmax];
priority_queue <int, vector<int>, comp> prq;
void init()
{
    int i;
    for(i = 1; i <= n; i++)
        cost_of_distance[i] = infinity;
}

void dijkstra(int nod_start)
{
    int nod;
    unsigned i, len;
    cost_of_distance[nod_start] = 0;
    prq.push(nod_start);
    while(!prq.empty())
    {
        nod = prq.top();
        prq.pop();
        checked[nod] = false;
        len = graphs[nod].size();
        for(i = 0; i < len; i++)
            if(cost_of_distance[graphs[nod][i].dest] > cost_of_distance[nod] + graphs[nod][i].cost)
            {
                cost_of_distance[graphs[nod][i].dest] = cost_of_distance[nod] + graphs[nod][i].cost;
                if(!checked[graphs[nod][i].dest])
                {
                    prq.push(graphs[nod][i].dest);
                    checked[graphs[nod][i].dest] = 1;
                }
            }
    }
}

int main()
{
    int i, a;
    dublu var;
    fin >> n >> m;
    init();
    for(i = 1; i <= m; i++)
    {
        fin >> a >> var.dest >> var.cost;
        graphs[a].push_back(var);
    }
    dijkstra(1);
    for(i = 2; i <= n; i++)
    {
        if(cost_of_distance[i] == infinity)
            fout << -1 << ' ';
        else fout << cost_of_distance[i] << ' ';
    }
    return 0;
}