#include <bits/stdc++.h>

using namespace std;
const int NMAX = 50005;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int, int>> graf[NMAX];
int n, m;
int dist[NMAX];
struct comp
{
    bool operator()(int a, int b)
    {
        return dist[a]<dist[b];
    }
};
void dij(int node)
{
    priority_queue<int, vector<int>, comp> cue;
    cue.push(node);
    fill(dist,dist+NMAX,INT_MAX);
    dist[node] = 0;
    while(cue.size())
    {
        int top = cue.top();
        cue.pop();
        for(auto i:graf[top])
        {
            if(dist[i.first]>dist[top]+i.second)
            {
                dist[i.first] = dist[top]+i.second;
                cue.push(i.first);
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int a, b, c;
        fin>>a>>b>>c;
        graf[a].push_back({b,c});
    }
    dij(1);
    for(int i = 2;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
    return 0;
}