#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<int,vector<int>,greater<int> > Q;

int Dist[100003],Marcat[100003];
void dijkstra(int n,int m)
{
    Q.push(1);
    for(int i=2;i<=n;i++)
        Dist[i]=1<<20;
    while(!Q.empty())
    {
        int n1=Q.top();
        Q.pop();
      //  if(Marcat[n1])
        //    continue;
        Marcat[n1]=1;
        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(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;
}