#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");ofstream fout("dijkstra.out");
//ifstream fin("date.in");ofstream fout("date.out");
vector<pair<int,int>>G[100003];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > Q;

int Dist[100003],Marcat[100003];
void dijkstra(int n,int m)
{
    Q.push(make_pair(0,1));
    for(int i=2;i<=n;i++)
        Dist[i]=1<<20;
    while(!Q.empty())
    {
        int n1=Q.top().second;
        Q.pop();
        if(Marcat[n1]==1)
            continue;
        Marcat[n1]++;
        for(int i=0;i<G[n1].size();i++)
        {
            if(Dist[G[n1][i].first]>Dist[n1]+G[n1][i].second)
            {
                Dist[G[n1][i].first]=Dist[n1]+G[n1][i].second;
                Q.push(make_pair(Dist[G[n1][i].first],G[n1][i].first));
            }
        }
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,xy;
        fin>>x>>y>>xy;
        G[x].push_back(make_pair(y,xy));
    }
    dijkstra(n,m);
    for(int i=2;i<=n;i++)
        if(Dist[i]==1<<20)
            fout<<"0 ";
    else
        fout<<Dist[i]<<" ";
    return 0;
}