#include <fstream>
#define nmax 50001
#define mmax 250001
#define inf 20000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[nmax];
struct muchie {int x,y,c;};
muchie G[mmax];

int main()
{f>>n>>m;
int i,ok=1;
for(i=1;i<=m;++i)
{
    f>>G[i].x>>G[i].y>>G[i].c;
    if(G[i].x==1) D[G[i].y]=G[i].c;
}
for(i=2;i<=n;++i) if(D[i]==0) D[i]=inf;
while(ok)
{
    ok=0;
    for(i=1;i<=m;++i)
    if(D[G[i].y]>D[G[i].x]+G[i].c) {D[G[i].y]=D[G[i].x]+G[i].c;ok=1;}
}
    for(i=2;i<=n;++i)
    if(D[i]!=inf) g<<D[i]<<' ';
    return 0;
}