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

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int oo = 2000000000;
const int NMax = 5005;
typedef pair<int, int> p;
int N, M, D[NMax];
vector <p> G[NMax];

struct Node
{
    int index, value;

    Node(int ind, int val)
    {
        index = ind;
        value = val;
    }

    bool operator<(const Node &other)const
    {
        return (value > other.value);
    }
};

priority_queue <Node> q;

void Read()
{
    in >> N >> M;
    for(int i = 1; i <= M;++i)
    {
        int a, b, c;
        in >> a >> b >> c;
        G[a].push_back(make_pair(a,b));
    }
}

void Solve()
{
    for(int i = 2;i <= N; ++i)                  //initializere pe infinit
        D[i] = oo;
    q.push(Node(1,0));
    while(!q.empty())
    {
        Node top = q.top();
        q.pop();
        if(top.value != D[top.index])
            continue;
        for(int i = 0;i < (int)G[top.index].size(); ++i)
        {
            p neighbour = G[top.index][i];
            if(D[neighbour.first] > D[top.index] + neighbour.second)
            {
                D[neighbour.first] = D[top.index] + neighbour.second;
                q.push(Node(neighbour.first, D[neighbour.first]));
            }
        }
    }
}

void Print()
{
    for(int i = 2; i <= N;++i)
        out << (D[i] != oo ? D[i] : 0) << ' ';
    out << '\n';
}

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