#define Dudica "Dudescu Alexandru"
#include <cstdio>
#include <vector>
#include <utility>
#define nmax 5000
#define inf 100000
using namespace std;
FILE *f1=fopen("dijkstra.in","r"),*f2=fopen("dijkstra.out","w");

vector <pair<int,int> > g[nmax];
int n,m,i,j,pre[nmax],d[nmax],x0=1;
bool use[nmax];

void citire()
{

    fscanf(f1,"%d%d",&n,&m);
    for(i=1;i<=n;i++)d[i]=inf;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        fscanf(f1,"%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
        if(x==x0)d[y]=c;
    }
    use[x0]=1;pre[x0]=0;
}
void dijkstra()
{
    int dmin,vfmin;
    for(j=1;j<n;j++)
    {
        dmin=inf;
        for(i=1;i<=n;i++)
            if(!use[i] && dmin>d[i])
        {
            dmin=d[i];
            vfmin=i;
        }
        use[vfmin]=1;
        for(i=0;i<g[vfmin].size();i++)
            if(!use[g[vfmin][i].first] && d[g[vfmin][i].first]>dmin+g[vfmin][i].second)
            d[g[vfmin][i].first]=dmin+g[vfmin][i].second;

    }
}
void afis()
{
    for(int i=2;i<=n;i++)
        fprintf(f2,"%d ",d[i]);
}
int main()
{
    citire();
    dijkstra();
    afis();
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.