#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#define mm 250001
#define nm 50001
#define mx 1001

using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}

int i,j,n,m,x,y,c,p,C[nm];
vector <pair<int,int> > g[nm];

void dj(int k)
{
    int j;
    for(j=0;j<g[k].size();j++)
    {
        if(C[k]+g[k][j].second<C[g[k][j].first])
         C[g[k][j].first]=C[k]+g[k][j].second;
    }
    for(j=0;j<g[k].size();j++)
     dj(g[k][j].first);
}


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++) stable_sort(g[i].begin(),g[i].begin()+g[i].size(),cmp);
    for(i=1;i<=n;i++) if(i!=1) C[i]=mx;
    dj(1); for(i=2;i<=n;i++) printf("%d ",C[i]%mx);
    return 0;
}