#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;

const int INF=1000000000;

vector <ii> g[50055];

priority_queue < ii,vector<ii>,greater<ii> > q;

ifstream in("djkstra.in");
ofstream out("djkstra.out");

int main()
{
    int n,m,i,j,di,x,y,z;
    ii f;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        g[x].push_back(ii(y,z));
    }
    vector <int> d(n+1,INF);
    d[1]=0;
    q.push(ii(0,1));
    while(!q.empty())
    {
        f=q.top();
        q.pop();
        di=f.first;
        x=f.second;
        if(di>d[x])
            continue;
        else
        {
            for(j=0;j<(int)g[x].size();j++)
            {
                y=g[x][j].first;
                z=g[x][j].second;
                if(d[x]+z<d[y])
                {
                    d[y]=d[x]+z;
                    q.push(ii(d[y],y));
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==INF)
            out<<"0 ";
        else
            out<<d[i]<<" ";
    }
    return 0;
}