#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define x first
#define y second
#define dm 50005
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct str{
    int node, cst;
    bool operator < (const str &other)const
        {return cst > other.cst;}
};
vector <pair <int,int> > v[dm];
priority_queue <str> pq;
int rd[dm];
int n, m;
void dijkstra()
{
    pq.push({1, 0});
    rd[1] = 0;
    while(!pq.empty())
    {
        int node = pq.top().node;
        int cst = pq.top().cst;
        pq.pop();
        if(cst != rd[node]) continue;
        for(auto it = v[node].begin(); it!=v[node].end(); it++)
        {

            int neighbor = (*it).first;
            int cost = (*it).second;
            if(rd[node] + cost < rd[neighbor])
            {
                rd[neighbor] = rd[node] + cost;
                pq.push({neighbor, rd[neighbor]});
            }
        }
    }
}
int main()
{
    int x, y, z;
    fin >> n >> m;
    memset(rd, inf, sizeof(rd));
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back(mp(y, z));
    }
    dijkstra();
    for(int i = 2; i <= n; i++)
    {
        if(rd[i]!= inf)
            fout << rd[i] << " ";
        else fout << '0' << " ";
    }
    return 0;
}