#include <bits/stdc++.h>
#define inf (1<<30)
#define NMAX 50005
#define price first
#define node second
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,dist[NMAX];
vector<pair<int,int> > a[NMAX];
set<pair<int,int> > heap;
void read()
{
    f>>n>>m; int x,y,d;
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>d;
        a[x].push_back(make_pair(d,y));
    }
}
void solve()
{
    for(int i=2;i<=n;i++)dist[i]=inf;
    heap.insert(make_pair(0,1));
    while(!heap.empty())
    {
        int node=heap.begin()->node;
        heap.erase(heap.begin());
        for(vector<pair<int,int> >::iterator it=a[node].begin();it!=a[node].end();++it)
        {
            int node2=it->node,d2=it->price;
            if(dist[node2]>dist[node]+d2)
            {
                if(dist[node2]!=inf)
                    heap.erase(heap.find(make_pair(dist[node2],node2)));
                dist[node2]=dist[node]+d2;
                heap.insert(make_pair(dist[node2],node2));
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]==inf)
        g<<0<<" ";
    else
        g<<dist[i]<<" ";
}
int main()
{
    read();
    solve();
    return 0;
}