#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

ifstream fi("dijkstra.in"); void Input();
ofstream fo("dijkstra.out"); void Output();

struct Arch
{
    int node;
    int weight;
    Arch(int aNode, int aWeight)
    {
        node = aNode;
        weight = aWeight;
    }

    bool operator <(const Arch & other) const
    {
        return weight > other.weight;
    }

};

priority_queue<Arch> q;
vector<Arch> graph[50000];
int dist[50000];
int n, m;

void ApplyDijkstra(int start)
{
    dist[start] = 0;
    q.push(Arch(start, 0));

    while(!q.empty())
    {
        auto x = q.top();
        q.pop();
        for(auto y:graph[x.node])
        {
            if(x.weight != dist[x.node])
                continue;

            if(dist[y.node] > dist[x.node] + y.weight)
            {
                dist[y.node] = dist[x.node] + y.weight;
                q.push(Arch(y.node, dist[y.node]));
            }

        }
    }
}



int main()
{
    Input();
    memset(dist, 0x3f3f3f3f, sizeof(int) * (n+1));
    ApplyDijkstra(1);
    Output();
}

void Input()
{
    fi>>n>>m;
    int a, b, c;
    for(int i = 1; i <= m; ++i)
    {
        fi>>a>>b>>c;
        graph[a].push_back(Arch(b,c));
    }
}
void Output()
{
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] == 0x3f3f3f3f)
            fo<<0<<' ';
        else
            fo<<dist[i]<<' ';
    }
}