#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct arc
{
    int d;
    int c;
};
const int nx=50002;
vector < arc > v[nx];
int dist[nx];
int n,m,i,j,c;
void dijkstra (int start)
{
    for(int i=2; i<=n; i++)
            dist[i]=INT_MAX;
    queue < int > q;
    q.push(start);
    while(!q.empty())
    {
        int i=q.front();
        q.pop();
        for(vector < arc > :: iterator it=v[i].begin(); it!=v[i].end(); it++)
            if(dist[it->d]>dist[i]+it->c)
        {
            dist[it->d]=dist[i]+it->c;
            q.push(it->d);
        }
    }
    for(int i=2; i<=n; i++)
        out<<(dist[i]==INT_MAX? 0 : dist[i])<<' ';
}
int main()
{
    in>>n>>m;
    for(;m;m--)
    {
        in>>i>>j>>c;
        v[i].push_back({j,c});
    }
    dijkstra(1);
    return 0;
}